# Uniquely $3$-edge-colourable $3$-regular graph with $\chi'(G) = 3$ has exactly $3$ Hamiltonian cycles?

As the title says, I am trying to show that a uniquely $3$-edge-colourable $3$-regular graph $G$ with edge-chromatic number $3$ has exactly $3$ Hamiltonian cycles.

I've managed to show the existence of three Hamiltonian cycles as follows: pick any $3$-colouring of the edges of $G$, then deleting the edges of a single colour, the resulting graph $G_1$ is $2$-regular, and hence its connected components are cycles. If there is more than one component, then swapping the colours in a single component of $G_1$ induces a different $3$-colouring of $G$, which is a contradiction; hence $G_1$ is a single cycle, and it is a Hamiltonian cycle on $G$.

I'm having trouble proving that the three Hamiltonian cycles I've found are unique, though. Let $C$ be a Hamiltonian cycle on $G$; I was thinking of trying to $2$-colour $C$ and then extend that to a $3$-colouring of $G$. If that can be done, then I think that by uniqueness of $3$-colourings, it follows that $C$ is one of the Hamiltonian cycles I've found earlier, but I'm having trouble constructing the $2$-colouring of $C$.

Any help is appreciated!

Removing a Hamiltonian cycle leaves a $1$-regular graph, which can be coloured with one colour. And the cycle itself can be coloured by $2$ colours, assigning the colours to alternate edges in the cycle. By uniqueness of the colouring, this cycle must have been obtained through the process you have described earlier.
• This takes me most of the way, but I don't understand why the cycle can always be $2$-coloured: what if the cycle has an odd number of edges? May 27, 2013 at 15:06