# Proof required for edges in a minimum spanning tree

G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

The answer is only statement 2 is correct.

I was able to prove statement 1 is false using contradiction. When we think of a complete graph with 4 vertices and edge weights 1,2,5,6 in non diagonal and diagonal edges 3 and 4. 4,5,6 will create a cycle and we can exclude the lighest edge e (4) from it, in a MST.

But statement 2 cannot be proved using the same. What should be the proof for proving statement 2 is correct?

• What have you tried? Where did you get stuck? Have you tried working through some small examples to look for patterns and try to build your intuition? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Also, see meta.cs.stackexchange.com/q/1284/755 – D.W. Nov 6 '16 at 18:32