GATE CS 2019 Q38 — Graphs: Connectivity, Matching, Colouring

Statement I is TRUE: If all edge weights in a connected, undirected graph $G$ are distinct, then $G$ has a unique minimum spanning tree (MST). This is a fundamental property of MSTs, which can be proved using the cycle property (the heaviest edge on any cycle cannot belong to any MST).

Statement II is TRUE: The Cut Property states that for any cut of a graph, the minimum-weight edge crossing the cut must belong to every MST. If for every cut there is a unique minimum-weight edge crossing it, then that specific edge must be included in every MST of $G$. Since the choice of the minimum-weight edge for every cut is unique, there is no ambiguity or alternative choice at any step of constructing the MST (e.g., in Prim's or Kruskal's algorithm), which guarantees a unique MST.

Thus, both statements I and II are TRUE.