# Prove that every 3-regular graph that contains a Hamiltonian cycle is always 3-edge colorable

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?

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.
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.