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.

  • $\begingroup$ Nice trick, thanks! Any ideas about the followup question (replacing "two" with a bigger number)? $\endgroup$ – Timothy Chow Jan 25 '13 at 15:12
  • $\begingroup$ Let me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs? $\endgroup$ – domotorp Jan 28 '13 at 13:27
  • $\begingroup$ Good question! I don't know, but this does seem to be a good place to start. I'll try asking on the domino mailing list. $\endgroup$ – Timothy Chow Jan 30 '13 at 16:31

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.