# On the analysis of Christofides's algorithm

Suppose you have even number of vertices, they form as a complete graph denote the graph by $$G$$. Now, suppose we compute the minimum weight perfect matching denoted by $$P$$ (so $$P$$ has alternating edges, i.e. one is a perfect matching and one is not along all the path $$P$$ through all vertices of $$G$$). Now, suppose $$T^*$$ is TSP tour of $$G$$.

Show that the inequality is true: $$\operatorname{cost}(P) \le \min \{ \operatorname{cost}(N_1), \operatorname{cost}(N_2) \},$$

where $$N_1$$ and $$N_2$$ are any two perfect matchings on $$T^*$$.

Note that this inequality from the analysis of Christofides's algorithm, see this nice paper.

• The weight of a minimum weight perfect matching is bounded by the weight of any perfect matching, by definition. – Yuval Filmus Feb 25 '18 at 13:38
• @YuvalFilmus Ahh I got the idea! I thought that $N_1$ and $N_2$ are only 'two edges' of the tour of TSP. with respect to you Yuval, if you Put your answer in answer section, I will check it! Thank you! – user777 Feb 25 '18 at 14:02

Since $P$ is a minimum weight perfect matching, by definition $$\operatorname{cost}(P) = \min_N \operatorname{cost}(N),$$ where $N$ goes overl all perfect matchings. In particular, $\operatorname{cost}(P) \leq \operatorname{cost}(N)$ for any particular perfect matching $N$.