GATE 2025 CS2 Q.37: solution and answer

Official answer: CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Since $G$ has $n$ vertices, every spanning tree of $G$ has exactly $n-1$ edges (a basic property of trees) — this holds for EVERY spanning tree, not just the MST.

2. After adding $\alpha$ to every edge weight, the new total weight of any spanning tree $T$ is ${\text{weight}}_{\text{new}}(T)={\text{weight}}_{\text{old}}(T)+\alpha (n-1)$, because $T$ contributes exactly $n-1$ edges to the sum, each of which increased by $\alpha$.

3. Crucially, the shift $\alpha (n-1)$ is the SAME constant for every spanning tree of $G$ — it depends only on $n$ and $\alpha$, never on which particular tree is chosen.

4. Adding an identical constant to every value in a set cannot change which value is the minimum. So whichever spanning tree(s) had minimum weight before the update still have minimum weight after it: every MST remains an MST.

5. Now consider shortest paths between two vertices $u$ and $v$. Unlike spanning trees, different candidate paths from $u$ to $v$ can use different numbers of edges — say one path uses $k_1$ edges and another uses $k_2\ne k_1$ edges.

6. After adding $\alpha$ to every edge, a path using $k$ edges gains total weight $k\alpha$. Since $k_1\ne k_2$ in general, the two candidate paths are shifted by DIFFERENT amounts, not the same amount as in the spanning-tree case.

7. This unequal shift can reverse the relative order: a path that was shortest before the update (possibly using more edges but a smaller original total weight) can end up longer than a path using fewer edges once $\alpha$ is added to every edge — a standard counterexample exists for any such setup.

8. Hence shortest paths need not remain shortest paths after the update, while every MST is guaranteed to remain an MST.

9. This matches option (C): Every MST remains an MST, and SPs need not remain SPs.