The GATE Grind

GATE 2019 CS – Question 48

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

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 above two statements is/are TRUE?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Both I and II

Explanation

Statement I is the standard uniqueness result for distinct weights. Statement II also holds: if every cut has a unique lightest crossing edge, then every MST must contain that edge (cut property), so the MST is unique.