2-conecta el gráfico contiene un camino que pasa a través de todos los impares grado de los vértices

Question

Estoy tratando de probar la de arriba como un ejercicio en el tema de la conectividad. He intentado hacerlo mediante el oído de descomposición, como grado impar de vértices puede ser caracterizado como puntos finales de las orejas, pero fue en vano. Las recomendaciones son apreciados. Gracias

Answer 1

La afirmación es falsa. Tome las siguientes $5$-gráfico regular (inspirado en el gráfico en este MathOverflow respuesta, que se $4$-regular no acababa de hacer el truco):

En este gráfico, cada grado es impar, por lo que estamos buscando un camino Hamiltoniano. Sin embargo, la visita a cada una de las cinco partes alrededor de los lados, tendríamos que ir por el medio de los vértices varias veces, así que esto es imposible.

Para un poco más de argumento formal: si un gráfico de $G$ tiene un camino Hamiltoniano, tiene un camino de $P_n$ como un subgrafo. La eliminación de los dos vértices de $P_n$ hojas en la mayoría de las $3$ componentes, por lo que el mismo debe ser cierto de $G$ (que es $P_n$ adicional de los bordes). Pero en la gráfica de arriba, la eliminación de los dos medio vértices hojas de $5$ componentes, por lo que no puede tener un camino Hamiltoniano.