Ciclos grandes en grafos cúbicos sin puentes

Question

Wikipedia nos dice que la mayoría de los grafos cúbicos tienen un cilindro de Hamilton (por ejemplo, la proporción de grafos hamiltonianos entre los grafos cúbicos en $2n$ vértices converge a 1 como $n$ va al infinito) pero también tiene la amabilidad de proporcionarnos algunas imágenes de grafos cúbicos no hamiltonianos:

Observando estos gráficos es fácil ver un patrón: en los tres casos hay un gran ciclo $C$ tal que todos los puntos no en $C$ tienen a sus tres vecinos en $C$ en lugar de estar conectados entre sí. (En los dos gráficos inferiores esto es más obvio.) Dado que lo mismo es algo vacuo para los gráficos cúbicos que hacer tienen un ciclo Hamilton mi pregunta es:

¿Es cierto que en todo grafo cúbico sin puentes conectado hay un ciclo $C$ de manera que cada vértice esté en $C$ o tiene sus tres vecinos en $C$ ?

(Por supuesto, también muchos vértices en $C$ tienen todos sus vecinos en $C$ así que, a pesar de escribir "o", aquí sólo me refiero al "o" ordinario e inclusivo, no al "o" exclusivo).

Edición: los gráficos de las imágenes se llaman "gráfico de Tutte", "gráfico de Coxeter" y "gráfico de Petersen", respectivamente.

Answer 1

Aunque esta pregunta parece no interesar a nadie, he pensado que sería bueno publicar aquí un contraejemplo que he encontrado desde que lo publiqué:

Supongamos (buscando una contradicción) que el gráfico contiene un ciclo $C$ de la forma descrita en la pregunta. Escogiendo cualquiera de las aristas rojas es fácil concluir que es absolutamente necesario que esta arista pertenezca a $C$ . Ahora, por simetría, los mismos argumentos se aplican a las otras aristas rojas y, por tanto, las 8 deben formar parte de $C$ . Esto implica a su vez que los vértices verdes no están en $C$ pero tienen exactamente 2 de sus vecinos en $C$ en lugar de 3, contradiciendo la presunta naturaleza de $C$ .