The GATE Grind

GATE 2016 CS – Question 50

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

$G = (V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees (MSTs) of $G$ is/are TRUE?

I. If $e$ is the lightest edge of some cycle in $G$, then every MST of $G$ includes $e$

II. If $e$ is the heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$

  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: (B) II only

Explanation

Statement II is true: the heaviest edge on any cycle is never in the minimum spanning tree when weights are distinct, because swapping it for a lighter edge of the cycle would reduce the weight. Statement I is false: the lightest edge of one cycle can still be left out of every MST, for example if it is the heaviest edge of a different cycle.