Given a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles.

Conversely when is it true that every union of even cycles comes from symmetric difference of perfect matchings?

Can we say anything at all for multipartite graphs?

The problem came from analyzing derandomizing weight assignments for perfect matching identification via determinants.

  • 2
    $\begingroup$ Symmetric difference of two perfect matchings is always a disjoint union of even cycles, not only in bipartite graphs, right? $\endgroup$ – Fedor Petrov Feb 26 '16 at 7:58
  • $\begingroup$ Fedor is quite right, but the problem might be more tractable in the bipartite case. $\endgroup$ – Brendan McKay Feb 26 '16 at 8:06
  • $\begingroup$ @BrendanMcKay made problem more general. $\endgroup$ – Turbo Feb 26 '16 at 8:07
  • 1
    $\begingroup$ So it is equivalent to: for which unions of even cycles is there a perfect matching using half the edges of each cycle. $\endgroup$ – Brendan McKay Feb 26 '16 at 8:10
  • $\begingroup$ yes there could be a graph with even cycles but no perfect matching at all. $\endgroup$ – Turbo Feb 26 '16 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.