I need to decompose any connected Regular graph into Hamiltonian cycles and Perfect matchings. Is there any theorem that guarantees this or is there any counter example to this ? If there is such theorem, then is there any algorithm to find decompositions ?


The ($3$-regular) Petersen graph is a counterexample. First we show that it cannot be properly edge-colored with three colors. That is we cannot color the edges with three colors so that no two edges of the same color share a common vertex. enter image description here

There is no way color three edges of the outer pentagon the same color without two of them intersecting, so we must have two pairs of edges the same color and the fifth edge a third color. WLOG we can color the outer edges as shown. This forces the edges leading from the outer pentagon to the inner star to be colored as shown. Now edge $57$ intersects a blue edge and a red edge so it must be colored green. (I see that edge $27$ looks more pink than red, but that's just some kind of foul-up. Consider it red.) Likewise, edge $79$ must be colored green. But these edges meet at vertex $7$ so a proper edge-coloring is not possible with three colors.

We can now show that the Petersen graph is not Hamiltonian. If there is a Hamilton cycle, color its edges alternately red and and green. Then we can color the remaining edges blue to get a proper edge-coloring with three colors, which we know is impossible.

Since the Petersen graph is not Hamiltonian, any decomposition of the type desired can only be a partition into three perfect matchings. If we have such a partition, we can color each edge according to the matching in which it occurs. Since each vertex occurs once in each partition, this gives a proper edge-color with three colors, which is impossible.

  • $\begingroup$ Thanks. Proof in bracket is for proving that there doesn't exist Hamiltonian cycle in Peterson graph given that there is no such coloring, right ? $\endgroup$ – MeetR Apr 20 at 15:43
  • 1
    $\begingroup$ Yes, that's correct. I'm about to edit my answer to make it more self-contained. $\endgroup$ – saulspatz Apr 20 at 15:48
  • $\begingroup$ Thank you for writing such a detailed answer. Nice proof. $\endgroup$ – MeetR Apr 20 at 16:27
  • $\begingroup$ @MeetR I enjoyed it. Thank you for the question. $\endgroup$ – saulspatz Apr 20 at 16:30

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.