Skip to main content
deleted 25 characters in body; edited tags; edited title
Source Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

Christofides algorithm: Whywhy 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

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

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

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...
Thanks in advance.

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.

Source Link
so.very.tired
  • 1.2k
  • 1
  • 15
  • 20

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...
Thanks in advance.