4
$\begingroup$

I would like to show the following:

Show that if a regular graph with degree 3 has a Hamiltonian cycle, then it has an edge colouring with three colours.

Is it correct to use the following reasoning:

  1. Since it has a maximum degree $k$, then at least $k$ colours are needed for an edge colouring of $G$
  2. (unsure) It seems that such a graph has to be bipartite. In this case, it's simple to use a theorem that states that the minimum colours needed is equal to max degree of $G$, i.e. in our case it's $3$.

Does the 1st statement give a lower bound or the minimum numbers of colours needed. Is the 2nd statement stronger?

Are there better ways of showing this statement?

$\endgroup$
1
  • 1
    $\begingroup$ Such a graph does not have to be bipartite. The complete graph $K_4$ is a counterexample. $\endgroup$
    – bof
    Commented Oct 14, 2016 at 9:11

1 Answer 1

12
$\begingroup$

By the handshaking lemma, the 3-regular graph must contain an even number of vertices, so the Hamiltonian cycle must be of even length; colour the edges of this cycle alternating two of the three colours. The remaining edges form a perfect matching in the graph; colour these edges with the third colour.

The image below shows this procedure applied to such a cubic Hamiltonian graph, the Dyck graph.

3-edge-colouring of the Dyck graph

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .