This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it.

I assume that a minimum spanning tree must have an even number of odd-degree vertices, since Christofides algorithm uses this fact to find a perfect matching between "the set of vertices with odd degree in $T$" - an impossible mission for a graph with odd number of vertices...

I couldn't convince myself why this is true, can someone please convince me? Either by a formal proof or with an informal explanation.

  • $\begingroup$ A graph can have an "odd number of vertices", but not an odd number of vertices with odd degree. $\hspace{.48 in}$ $\endgroup$ – user12859 Mar 17 '15 at 12:06
  • $\begingroup$ @RickyDemer, what I meant there is that a graph with an odd number of vertices in it cannot have perfect matching. $\endgroup$ – so.very.tired Mar 17 '15 at 13:51

Every edge in a graph is incident with exactly two vertices. The degree of a vertex is the number of edges incident with it. From this you get the standard fact that the sum of all the vertex degrees in a graph equals twice the number of edges; in particular, it is even. A minimum spanning tree is a graph in its own right. If it had an odd number of odd-degree vertices, the sum of degrees would be odd, which is impossible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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