8
$\begingroup$

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!

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Jonas
    May 27, 2013 at 15:06
  • 1
    $\begingroup$ Number of vertices must be even here, as each degree is odd and degree sum must be even. $\endgroup$
    – polkjh
    May 27, 2013 at 15:08
  • $\begingroup$ I get it now. Thanks for the help! $\endgroup$
    – Jonas
    May 27, 2013 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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