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

Given a 2

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