¿Una subdivisión de un gráfico de Hamilton es también un gráfico de Hamilton?

Question

¿Qué debo hacer para demostrarlo? Creo que la respuesta es sí, ya que subdividir un gráfico no afecta a los ciclos que tiene: Al ir del nodo a al b, una subdivisión de 1, por ejemplo, simplemente te hará ir de a a v a b. Pero me falta una idea para demostrarlo formalmente.

Answer 1

De hecho, existe un grafo hamiltoniano $H$ cuya subdivisión no es hamiltoniana.

Pista: Que $v_1v_2 \ldots v_7$ ser un $7$ -ciclo. A continuación, añada el vértice $y_1$ y los bordes $v_7y_1$ y $y_1v_1$ . Saca esto; $v_1v_2 \ldots v_7$ es un $7$ -ciclo y $v_7y_1v_1$ forman un triángulo. Entonces este gráfico resultante $H$ tiene $8$ vértices y un ciclo hamiltoniano $v_1v_2 \ldots v_7y_1$ .

¿Y si subdividieras cada uno de los bordes $v_7v_1, v_7y_1$ y $y_1v_1$ de $H$ Sin embargo ¿Sigue siendo hamiltoniano el gráfico resultante? [Deberías ver que la respuesta es No].