1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Mar 17, 2015 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
    Commented Mar 17, 2015 at 13:51

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0

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.