0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – D.W. ♦
    Commented Nov 6, 2016 at 18:32

1 Answer 1

Reset to default
1
$\begingroup$

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? May it be the case that another edge in the cycle can play the 'role' of e in MST?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.