= Minimum-weight perfect matching
{title2=$\min_M\sum_{e\in M}c_e$}
A minimum-weight <perfect matching> pairs every vertex exactly once while minimizing total edge weight. General weighted <perfect matching> has polynomial-time algorithms. In the <Christofides algorithm>, it corrects precisely the odd-degree vertices of a <minimum spanning tree>. Alternating edges of a cyclic order on an even number of vertices give two <perfect matchings>; the cheaper one costs at most half that cycle's cost.
Back to article page
