Basic Questions about Minimum Spanning Tree

Question

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?

Answer 1

I don't think your claims are valid. The problem is that you are only considering a cycle in a larger graph.

Consider for example a graph G consisting of 6 nodes in a cycle (with random weights >1). Your claims might hold for that graph but now add 1 node in the center of the graph and connect it with 6 links of cost 1. The MST of your entire graph now will consist of only those 6 edges (which form a star).

If you now look at your claims, you'll see:

• The lightest edge in your cycle does not belong to the MST (=star)
• None of the edges in the cycle are in the MST

Answer 2

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

Answer 3

The first one of your claims is always true. The lightest edge is on the MST for any graph.

The second one is not always true. It is always true if the entire graph is a cycle and thus every node has 2 edges incident to it. However, in the general case, an edge (u,v) of weight k is never on MST whenever there is a path between the nodes u and v connecting them at a total weight less than k.