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?