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.
Christofides algorithm: why must an MST have even number of odd-degree vertices?
graph theory;minimum spanning tree
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.