1
$\begingroup$

A graph $G$ is $k$-edge colorable if there exists a function $f\colon E(G) → [k]$ s.t $f(e) \neq f(e')$ whenever $e$ and $e'$ share a vertex. A Hamiltonian cycle in an $n$-vertex graph is a sub-graph isomorphic to $C_n$. Finally, a graph $G$ is $d$-regular if $\deg_G(v) = d$ for every $v ∈ V (G)$.

Prove that every 3-regular graph that contains a Hamiltonian cycle is always 3-edge colorable. Also, does this apply more generally to say that any $n$-regular graph with a Hamiltonian cycle is $n$-edge colorable?

$\endgroup$
2
$\begingroup$

A $3$-regular graph has an even number of vertices. Therefore the edges of the Hamiltonian cycle can be properly colored with $2$ colors. The remaining edges form a matching, so they can be given a third color.

The graph $K_5$ is a $4$-regular graph with a Hamiltonian cycle but it is not $4$-edge colorable.

$\endgroup$
0
$\begingroup$

Per handshaking, $2e=3n$, i.e., $n$ is even. Therefore the $C_n$ of the Hamitonian cycle is 2-colourable. Assigne the third colour to all edges not belonging to the Hamiltonian cycle.

This does not generalize: $K_5$ is Hamiltonian and 4-regular, but not 4-edge-colourable.

$\endgroup$

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.