Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. 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

GATE 2019 · Discrete Mathematics · Graph Connectivity · medium

Answer: C. Both I and II are TRUE.

1. Verify Statement I: distinct weights imply unique MST: In Kruskal's algorithm, edges are sorted by weight. Since all weights are distinct, at each step only one edge is the current minimum safe edge to add. No tie-breaking is needed, so the MST is unique.
2. Verify Statement II: unique min cut edge implies unique MST: By the cut property, the minimum-weight edge crossing any cut must be in every MST. If each cut's minimum edge is unique, there is no freedom in choosing different edges, so the MST is forced to be unique.
3. Conclusion: Both Statement I and Statement II are true. The answer is C.