Let 𝐺 be any connected, weighted, undirected graph. I. 𝐺 has a unique…
2019
Let 𝐺 be any connected, weighted, undirected graph.
I. 𝐺 has a unique minimum spanning tree, if no two edges of 𝐺 have the same weight.
II. 𝐺 has a unique minimum spanning tree, if, for every cut of 𝐺, there is a unique minimum-weight edge crossing the cut.
Which of the above two statements is/are TRUE?
- A.
I only
- B.
II only
- C.
Both I and II
- D.
Neither I nor II
Attempted by 238 students.
Show answer & explanation
Correct answer: C
Answer: Both statements are true.
Statement I: If all edge weights are distinct, the MST is unique. Reason: distinct weights prevent any tie when choosing the minimum edge across a cut (for example in Kruskal's algorithm). If there were two different MSTs, consider the smallest-weight edge that belongs to one but not the other; swapping edges yields a contradiction to minimality.
Statement II: If every cut has a unique minimum-weight edge crossing it, that edge must be included in every MST by the cut property. Because the light edge of each cut is forced, the collection of required edges is fixed and any MST must be the same, so the MST is unique.
Conclusion: Both conditions independently guarantee a unique minimum spanning tree.
A video solution is available for this question — log in and enroll to watch it.