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

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