# Christofides algorithm: why must an MST have even number of odd-degree vertices?

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.

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

## 1 Answer

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.