# 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? – Jonas May 27 '13 at 15:06