Prueba de Bondy y Chvátal Teorema

Question

Un gráfico es hamiltoniano si y solamente si su cierre es hamiltoniano.

Estoy en busca de una prueba (es decir, breve) simple del teorema, que puedo utilizar como parte de un artículo sobre clasificación topológica.

No he podido encontrar una en la tienen acceso a la literatura. Cualquier ayuda sería apreciada.

Answer 1

Sea G=G_0, G_1, G_2, etc ser una secuencia de gráficos donde cada G_i es formado mediante la realización de un solo cierre el paso a G_{i-1}, es decir, añadir un borde uv para G_i cuando u y v en conjunto tienen al menos n vecinos. Si cualquier gráfico en esta secuencia es Hamiltoniano, sea k el mínimo de k tal que G_k es Hamiltoniano. Entonces yo reclamo que k=0. Para, de lo contrario vamos a uv ser el borde agrega para formar G_k de G_{k-1} y dejar que C sea un ciclo Hamiltoniano en G_k. Hay n-1 otras aristas en C, y n los bordes de salir de la u y v juntos, así que por el principio del palomar existe un borde pq en C (con el vértice de etiquetado elegido de modo que u es hacia la derecha de v y p es hacia la derecha de q) tales que G_{k-1} contiene bordes y vq. Pero entonces C + + vq - pq - uv es un ciclo Hamiltoniano en G_{k-1} contradiciendo la suposición de que k > 0.

Answer 2

Permítanme reformular el teorema de las variables.

La notación de Leer $p\bowtie q$ " $p$ es adyacente a $q$", $p\not\bowtie q$ " $p$ no es adyacente a $q$".

Teorema Deje $G$ un gráfico cuyo orden es mayor que $2$. Deje $v_1$ $v_2$ ser vértices tal que $v_1\neq v_2 \land v_1\not\bowtie v_2$$\deg v_1 + \deg v_2 \ge n\in\mathbb{N}$. A continuación, $G$ es Hamiltoniano iff $G' = G + v_1 v_2$ es de Hamilton.

Prueba de Asumir $G'$ es de Hamilton, pero no $G$. Por lo tanto, por definición, existe un ciclo de $(p_1,\ldots,p_n)$ $G$ conectar $v_1$ (a $p_1$) $v_2$ (a $p_n$) en la visita a todos los de $G$'s de vértices. Si $p_k\bowtie p_1$$p_{k-1} \not\bowtie p_n$, ya que el $(p_1,p_k,p_{k+1},\ldots,p_n,p_{k-1},p_{k-2},\ldots,p_1)$ es un ciclo Hamiltoniano de $G$. Como tal, $\deg p_n \le n - (1 + \deg p_1)$, una contradicción.