GATE CSE 2019 | Question: 38

Question

Let $G$ be any connected, weighted, undirected graph.

1. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight.
2. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut.

Which of the following statements is/are TRUE?

• A. I only
• B. II only
• C. Both I and II
• D. Neither I nor II

Comments

Cut in Minimum spanning Tree:

https://www.baeldung.com/cs/minimum-spanning-tree-cut

---

what is wrong in my example please anyone explain ? 

bcoz in last example there is more than one spanning tree possible

---

@Ray Tomlinson they are asking about "EVERY" cut in 3rd graph {4,5},{4,6} edge is also a cut which have same weight.

Answer 1

If for every cut of a graph there is a unique minimum weight edge crossing the cut,
then the graph has a unique minimum spanning tree.

This statement is true and can be proved ea sily by contradiction.

Answer 2

If edge wt. are distinct then the graph will have unique MST but the converse of this statement (statement 1 of question) is not true. 

The graph can have unique MST even though it has repeated edge weights. 

So, statement 1 is False.