Únicamente $3$ -Bordes coloreables $3$ -grafo regular con $\chi'(G) = 3$ tiene exactamente $3$ ¿Ciclos hamiltonianos?

Question

Como dice el título, estoy tratando de mostrar que un $3$ -Bordes coloreables $3$ -Gráfico regular $G$ con número cromático de borde $3$ tiene exactamente $3$ Ciclos hamiltonianos.

He conseguido demostrar la existencia de tres ciclos hamiltonianos de la siguiente manera: elige cualquier $3$ -coloración de los bordes de $G$ y eliminando las aristas de un solo color, el gráfico resultante $G_1$ es $2$ -regular, y por lo tanto sus componentes conectados son ciclos. Si hay más de un componente, el intercambio de colores en un solo componente de $G_1$ induce a una $3$ -coloración de $G$ que es una contradicción; por lo tanto $G_1$ es un ciclo único, y es un ciclo hamiltoniano en $G$ .

Sin embargo, tengo problemas para demostrar que los tres ciclos hamiltonianos que he encontrado son únicos. Dejemos que $C$ sea un ciclo hamiltoniano en $G$ Estaba pensando en intentar $2$ -color $C$ y luego extenderlo a un $3$ -coloración de $G$ . Si eso se puede hacer, entonces creo que por unicidad de $3$ -colores, se deduce que $C$ es uno de los ciclos hamiltonianos que he encontrado antes, pero tengo problemas para construir el $2$ -coloración de $C$ .

Se agradece cualquier ayuda.

Answer 1

La eliminación de un ciclo hamiltoniano deja un $1$ -Gráfico regular, que puede ser coloreado con un color. Y el propio ciclo se puede colorear con $2$ colores, asignando los colores a aristas alternas en el ciclo. Por la singularidad de la coloración, este ciclo debe haberse obtenido mediante el proceso que ha descrito anteriormente.