0
$\begingroup$

Is there a counter example or proof for the claim that the lightest edge-disjoint union of a pair of perfect matchings contains the edges of the lightest perfect matching in a finite complete graph with $2n$ vertices and positive edge-weights?

$\endgroup$
2
  • $\begingroup$ The context here is a weighted graph? $\endgroup$ Apr 13 at 12:25
  • $\begingroup$ @GerryMyerson yes, sorry if that isn't clear from the question; I will edit the question accordingly. $\endgroup$ Apr 13 at 12:31
4
$\begingroup$

The following should give a counterexample: enter image description here

Make the black edges cost 1, green edges cost 2, and purple edges cost 1 billion. Make all other edges cost 10 trillion so we can safely ignore them (thus this counter example also works for the version of the question concerning complete bipartite graphs).

The minimum perfect matching is the three black edges, but any edge-disjoint union of two perfect matchings that contains the black edge perfect matching also must contain at least one purple edge. Whereas you can for instance instead get an edge-disjoint union of two perfect matchings that's the 4 green edges plus the bottom and top black edges.

$\endgroup$
1
  • $\begingroup$ Very nice! The simplest things are the best in life, that's why they're so hard to find. $\endgroup$ Apr 14 at 2:57

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.