Can we decompose any connected Regular graph (or subclass of it) into Hamiltonian cycles and Perfect matchings?

Question

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 ?

Answer 1

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.

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.