Search code examples
algorithmlanguage-agnosticgraphminimum-spanning-tree

Basic Questions about Minimum Spanning Tree

This is not a homework. I am trying to do exercises from a textbook to understand MST (minimum spanning tree).

Suppose I have a cycle C in a weighted undirected graph G. As I understand, the following is correct:

  • The heaviest edge in C belongs to no MST of G. That is, there is no MST of G, which contains that edge.
  • The lightest edge in C belongs to some MST of G. That is, there is an MST of G, which contains that edge.

Now I wonder if the followings claims are correct too.

  • The lightest edge in C belongs to all MST of G. That is, there is no MST of G, which does not contain that edge.
  • Any edge in C except the heaviest one belongs to some MST. That is, for each edge in C except the heaviest one there is an MST, which contains that edge.

Could you prove the last claim?

Solution

  • Even for the first claim if there are multiple edges which are lightest, all need not be included in the MST.