The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.


The objective is to determine a perfect matching $\mathrm{M}\_{\text{opt}}$ of minimal weight.


Consider now the greedy heuristic that determines a perfect matching $\mathrm{M}\_{\text{app}}$ by starting with $\mathrm{M}\_{\text{app}}\,=\,\emptyset$ and keeps adding the shortest edge that is not adjacent to any edge in $\mathrm{M}\_{\text{app}}$ until it is a perfect matching.



> 
> **Question:**
> 
> 
> Is it true, that the longest edge in $\mathrm{M}\_{\text{opt}}$ can't be strictly longer than the longest edge in $\mathrm{M}\_{\text{app}}$?
> 
> 
> 


I am convinced that that must be true for the following reason: if $\mathrm{M}\_{\text{opt}}$ contains a longer edge, then it must also contain an edge that compensates for the weight difference and is not contained in $\mathrm{M}\_{\text{app}}$.  

As the shortest edge is already contained in $\mathrm{M}\_{\text{app}}$ it can't be the edge that compensates for the weight difference; therefore it must be adjacent to some shorter edge in $\mathrm{M}\_{\text{app}}$, which completes the proof; is that actually the case?


  

If the longest edge of $\mathrm{M}\_{\text{opt}}$ can't indeed be longer than the longest edge of $\mathrm{M}\_{\text{app}}$ the performance of matching algorithms could in some cases be improved substantially by reducing the number of candidate edges



Edge-length constraints from greedy matching
Let the weights of the edges in a 6-cycle in $K\_6$ be $1,2,5,6,5,2$ (in cyclic order), and let other weights be large. Then the optimal matching will be $2,2,6$, while the greedy one will consist of $1,5,5$.


A similar construction works with longer cycles.


