Son todos $4$-regular los gráficos hamiltonianos

Question

Es fácil demostrar que todos los conectados $2$-regular gráficos son hamiltonianos. La gráfica de Petersen es una gráfica de $3$-regular que no es hamiltoniano. ¿Hay cualquier $4$ gráficos regulares que no son hamiltonianos?

Gracias

Answer 1

La respuesta es no. El gráfico en el cuadro es el contraejemplo más pequeño

Probablemente puede generalizar esta construcción cada $k > 4$ y deducir que siempre se pueden encontrar conectado %#% gráficos #%-regular que no son hamiltonianos.

Answer 2

Tenga en cuenta que usted no especificar conectado gráfico, que sin duda es necesario para Hamiltonicity. Más en general, un ciclo de Hamilton tiene la propiedad de que la eliminación de cualquier $k$ vértices rompe el ciclo en la mayoría de los $k$ de los componentes conectados. En el caso de $k=1$ un Hamiltoniano gráfico debe ser firmemente conectado.

Elija su favorito $4$-gráfico regular $G$, y eliminar una arista $e$, por lo que tiene dos vértices de grado $3$. Tomar dos copias de $G-e$, y crear un nuevo vértice es adyacente a los cuatro deficiencia de vértices. El gráfico resultante es $4$-regular, conectado, pero no está firmemente conectado.

También, intenta Googlear 4-regular no Hamiltoniano? El Meredith gráfico es muy fuertemente conectado, $4$-regular y todavía no Hamiltonianos.

Answer 3

Sin embargo, Tutte demostró que un gráfico planar conectado 4 es hamiltoniano.