# Non-unique 2-factorization of 2k-regular graphs

Petersen proved that every 2k-regular graph is 2-factorable. The factorization is in general not unique.

Given a 2k-regular graph, is it possible to move from any 2-factorization to any other 2-factorization by altering two 2-factors at a time?

If we broaden the question to multigraphs then the answer is no; consider the multigraph on three vertices with two edges between each pair of vertices and a loop on each vertex. This suggests that the answer is no even for graphs. In fact a colleague of mine suspects:

The answer is no even if we change "two" to any bounded number

(where by "two" here I mean only the number of factors being altered simultaneously, not the "2" in "2-factor"). However, we don't know how to prove or disprove this.

The motivation for this question comes from a conjecture in representation theory but the connection is rather convoluted so I will omit the details here.

No and in fact your multigraph construction is the counterexample. Just replace each edge with an "almost 6-regular" graph, like $K_7$ minus one edge, uv, and connect u and v respectively to the endpoints of the original edge.