GATE CS 2025 Set 2 | Question 37

MCQ · 2 marks · −0.66

Let \(G\) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \(\alpha\) is added to the weight of every edge.

Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \(G\) before and after the edge weight update?

  1. Option A: Every MST remains an MST, and every SP remains an SP.
  2. Option B: MSTs need not remain MSTs, and every SP remains an SP.
  3. Option C: Every MST remains an MST, and SPs need not remain SPs. (correct)
  4. Option D: MSTs need not remain MSTs, and SPs need not remain SPs.

Answer

(C)

Explanation

MSTs stay. Every spanning tree of a connected graph with \(n\) vertices has exactly \(n - 1\) edges, so every spanning tree gets heavier by the same amount, \((n - 1)\alpha\). Their order by weight does not change, so every MST remains an MST.

SPs can change. A path with \(k\) edges gets heavier by \(k\alpha\), so paths with more edges are penalised more. Take edges \(uv\) and \(vw\) of weight 1 and an edge \(uw\) of weight 3. The shortest path from \(u\) to \(w\) is \(u, v, w\) with weight 2. After adding \(\alpha = 2\) it weighs 6, while the single edge \(uw\) weighs 5, so the old SP is no longer shortest.

Answer: C