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?
$\begingroup$
$\endgroup$
2
asked Apr 12, 2021 at 15:35
-
$\begingroup$ The context here is a weighted graph? $\endgroup$– Gerry MyersonApr 13, 2021 at 12:25
-
$\begingroup$ @GerryMyerson yes, sorry if that isn't clear from the question; I will edit the question accordingly. $\endgroup$– Manfred WeisApr 13, 2021 at 12:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The following should give a counterexample:
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.
answered Apr 13, 2021 at 17:36
-
$\begingroup$ Very nice! The simplest things are the best in life, that's why they're so hard to find. $\endgroup$ Apr 14, 2021 at 2:57