Demostrar que si $deg (v) > \frac{k}{2}$ por cada $v \in V(G)$ entonces $G$ es hamitoniano.

Question

Dejemos que $G$ sea un grafo bipartito con conjuntos partitivos $U$ y $W$ tal que $|U|=|W|=k \geq 2$ . Demostrar que si $deg (v) > \frac{k}{2}$ por cada $v \in V(G)$ entonces $G$ es hamitoniano.

Teorema de Dirac : Sea $G$ sea un gráfico de orden $n$ tal que $deg(v) \geq \frac {n}{2}$ para cada vértice $v$ en $G$ entonces $G$ es hamiltoniano.

aquí está mi prueba

Dejemos que $G$ sea un grafo bipartito con conjuntos partitivos $U$ y $W$ tal que $|U|=|W|=k \geq 2$ . . Ya que $G$ sea un grafo bipartito con conjuntos partitivos $U$ y $W$ tal que $|U|=|W|=k \geq 2$ , $G$ tiene orden $2k$ . Sea $V(U)=\{u_1, \dots, u_k\}$ y $V(W)=\{w_1, \dots, w_k\}$ Supongamos que $G$ no es hamiltoniano. Todavía necesito la afirmación de que $G$ está conectado. Sea $P$ sea la trayectoria máxima en $G$ , por lo que tenemos $P$ es el camino en zigzag que parte de $u_1$ y terminan en $w_k$ . Desde $deg(v) \geq \frac {k}{2}$ para cada vértice $v$ en $G$ , $u_1$ debe ser adjunto a algún vértice $v_i$ y $v_k$ debe ser adjunto a algún vértice $u_i$ para $1<i<k$ . Y siempre encontramos un ciclo hamiltoniano. Así que es imposible graficar $G$ sin contener un ciclo hamiltoniano.

Answer 1

Empecemos por suponer, por el contrario, que existen grafos que cumplen las condiciones pero que no son hamiltonianos. De todos estos grafos que actúan como contraejemplos de nuestro teorema, dejemos que G sea uno de tamaño máximo (es decir, que la adición de cualquier arista dé lugar a un ciclo hamiltoniano). Sea x un vértice en U y sea y un vértice en W y que estos dos vértices sean no adyacentes. Entonces, xy no puede ser una arista o producirá un ciclo hamiltoniano en G. Por lo tanto, debe haber un camino hamiltoniano x-y en G.

Ahora bien, sea u* un vértice de u adyacente a y, entonces u* no puede ser adyacente a un vértice adyacente a x o de lo contrario habrá un ciclo hamiltoniano (este detalle aún debe ser limado, pero estoy bastante seguro de que, con un poco más de precisión, este hecho es cierto). Así, Deg u* <= k-deg x. pero deg x >n/2, por lo que deg u* es menor que k/2. Esto es una contradicción, por lo que debe ser el caso de que el resultado se mantiene.

Answer 2

Esta demostración se basa en una demostración bastante estándar del teorema de Dirac. Por desgracia, es más larga de lo que esperaba. Tal vez estoy pasando por alto algo.

Reclamación 1: $G$ está conectado.

Prueba de la afirmación 1: cada vértice es adyacente a más de $\frac k2$ vértices en el otro conjunto de partición, por lo que incluso el componente más pequeño tiene más de $k$ vértices. Dado que sólo hay $2k$ vértices en conjunto, sólo puede haber un componente.

Afirmación 2: Sea $P$ sea una trayectoria máxima y suponga $P$ tiene $2m+1$ vértices. Entonces no puede haber un ciclo con $2m$ vértices.

Prueba de la afirmación 2: Supongamos que $C$ es un ciclo con $2m$ vértices. Si hay un vértice que no está en $C$ que tiene un vecino que no está en $C$ , encontramos un camino de longitud mínima $2m+2$ . Contradicción. Así que cada vértice que no está en $P$ tiene todos sus vecinos en $C$ . Desde $C$ tiene tantos vértices de $U$ a partir de $W$ hay un vértice $u\in U$ y un vértice $w\in W$ que no están en $C$ . Ambos tienen más de $\frac k2$ diferentes vecinos en $C$ y como $C$ tiene $2m<2k$ vértices, dos de ellos deben ser adyacentes (!), digamos $x$ (vecino de $u$ ) y $y$ (vecino de $w$ ). Pero entonces encontramos un camino de longitud $2m+2$ (empezar en $u$ Ir a $x$ , toma el camino largo en $C$ a $y$ y, a continuación, vaya a $w$ ). Esta última contradicción demuestra la afirmación 2.

Afirmación 3: No puede haber una trayectoria máxima con $2m+1$ vértices.

Prueba de la afirmación 3: Supongamos que existe un camino maximal $P$ . Podemos suponer que tiene $m+1$ vértices en $U$ y $m$ en $W$ . Etiquetar los vértices $u_0,w_1,u_1,\ldots,w_m,u_m$ . Ahora ambos $u_0$ y $u_m$ tienen más de $\frac k2$ vecinos en $P$ (o $P$ no sería máxima) y todos ellos están entre $w_1,\ldots,w_m$ . Si $u_0$ es adyacente a $w_i$ entonces $u_m$ no puede ser adyacente a $w_{i-1}$ , porque encontraríamos un ciclo de $2m$ vértices, contradiciendo la afirmación 2. Por lo tanto, dado que $u_0$ tiene más de $\frac k2$ vecinos en $P$ (entre los $w_i$ ), $u_m$ tiene al menos (no "más" sino "al menos" para cubrir $w_0$ ) $\frac k2$ no vecinos en $P$ (entre los $w_i$ ), pero entonces no puede tener $k$ vecinos en $P$ (entre los $w_i$ ), ya que $m<k$ . Contradicción.

Ahora, las dos últimas afirmaciones son más del mismo tipo de argumento y te dejo las pruebas a ti.

Afirmación 4: Que $P$ sea una trayectoria máxima de $2m$ vértices, entonces $G$ tiene un ciclo de $2m$ vértices.

Prueba de la afirmación 4: Supongamos que no existe tal ciclo. Los vértices de $P$ Alternar entre las partes. Etiquételas $u_1,w_1,\ldots,u_m,w_m$ . $u_1$ tiene al menos $\frac k2$ vecinos entre los $w_i$ . Si $w_i$ es vecino de $u_1$ , entonces $u_i$ no puede ser vecino de $w_m$ (o encontramos un ciclo de longitud $2m$ ). Dado que $u_1$ tiene al menos $\frac k2$ vecinos entre los $w_i$ , $w_m$ tiene al menos $\frac k2$ no vecinos entre los $u_i$ . Pero entonces no puede tener más de $\frac k2$ vecinos entre los $u_i$ desde $m\leq k$ . Contradicción.

Afirmación 5: Que $P$ sea una trayectoria máxima y suponga $P$ tiene $2m$ vértices. Si hay un ciclo con $2m$ vértices, entonces $m=k$ .

Prueba de la afirmación 5: Sea $C$ sea un ciclo con $2m$ vértices. Si hay un vértice $v$ que no está en $C$ hay un camino desde $v$ a $C$ y podemos abrir el ciclo para conseguir un camino más largo. Contradicción. Así que cada vértice está en el ciclo y hemos terminado.

Juntos, los reclamos prueban su ejercicio. Hazme saber si hay partes que no puedes terminar.