This is a follow-up question to Minimum-weight disjoint union of perfect matchings:
- let $G$ be a complete symmetric graph with $2n$ vertices, whose edges are mapped to their weights by $\omega()$ and let
- $M_1$ the minimum-weight perfect matching of $G$
- $M_{i+1}$ the minimum-weight perfect matching of $G\setminus\bigcup\limits_{j=1}^{i}M_j$
Question:
does the assumption that $\bigcup\limits_{j=1}^{i}M_i$ is optimal, but $\bigcup\limits_{j=1}^{i+1}M_i$ is not imply the existence of a pair of edges $(a,c)\in \bigcup\limits_{j=1}^{i}M_i,\ (b,d)\in M_{i+1}$ s.t. $\omega(a,b)+\omega(c,d)\lt \omega(a,c)+\omega(b,d)\ \lor\ \omega(a,d)+\omega(b,c)\lt \omega(a,c)+\omega(b,d)$,
i.e. that $\bigcup\limits_{j=1}^{i+1}M_i$ must contain a pair of crossing edges?
