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.

  • $\begingroup$ The weight of a minimum weight perfect matching is bounded by the weight of any perfect matching, by definition. $\endgroup$ Feb 25, 2018 at 13:38
  • $\begingroup$ @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! $\endgroup$
    – user777
    Feb 25, 2018 at 14:02

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.