Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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
Number of vertices must be even here, as each degree is odd and degree sum must be even. – polkjh May 27 '13 at 15:08
I get it now. Thanks for the help! – Jonas May 27 '13 at 15:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.