Minimum-weight perfect matching (${\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.