Si un grafo tiene un Camino de Hamilton que comienza en cada vértice, ¿debe contener un Circuito de Hamilton?

Question

Si un grafo $G$ tiene al menos tres vértices y tiene un Camino de Hamilton empezando en cada vértice, ¿debe contener un Circuito de Hamilton?

He estado luchando con este problema. Parece que dado que cada vértice tanto comienza como no comienza un Camino de Hamilton, cada vértice está contenido en un circuito. Pero no puedo extender esta idea para demostrar que hay un Circuito de Hamilton.

Answer 1

El grafo de Petersen es un contraejemplo a tu problema. Todos los vértices son similares y es fácil encontrar un camino hamiltoniano. Pero no hay ciclo hamiltoniano en este grafo.

Creo que es el ejemplo más pequeño pero no tengo una prueba.

Puedes demostrar fácilmente que todos los vértices deben tener grado al menos 2 (si un vértice tiene grado 1, entonces no hay camino hamiltoniano que empiece en su único vecino).

Por lo tanto, el contraejemplo más pequeño tiene todos los vértices de grado al menos 2. Además, no tiene vértices de corte (no hay camino hamiltoniano que empiece desde un vértice de corte) y no tiene aristas puente.

Answer 2

Pista: intenta construir un grafo que tenga un camino de Hamilton que comience en cada vértice pero que tenga un vértice de grado uno. Tal grafo no tendrá un circuito de Hamilton.

EDICIÓN: Como señala Marc van Leeuwen a continuación, esto es completamente falso. El contraejemplo de Aline Parreau funciona claramente: ¡como siempre, cuando tengas dudas, prueba con el grafo de Petersen!