3
$\begingroup$

I need to show that a 3-regular Hamiltonian graph is 3-edge-colorable.

I figured I could start by constructing a Hamiltonian cycle. Every vertex in this cycle is connected with two other vertices, so you would need two or three colors to color all edges within this cycle (depending on the number of vertices/edges). But our graph isn't 2-regular, it's 3-regular, so I need to prove that I don't need a fourth color for the remaining edges. I don't know how to proceed from here. I can show that the remaining edges can all have the same color, because they don't meet, but how do I show that I don't need an extra color aside from the ones I already used for the hamiltonian cycle?

Edit: I found out that the hamiltonian cycle should be 2-edge colorable, because 3-regularity implies an even hamiltonian cycle. I don't quite follow why the cycle should be even.

$\endgroup$
5
$\begingroup$

Hint: any $3$-regular graph has an even number of vertices, because the sum of degrees is twice the number of edges.

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