Christofides algorithm: why must an MST have even number of odd-degree vertices?
-
02-11-2019 - |
Question
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.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange