GATE CS 2025 Set 2 Q27 — Minimum Spanning Trees

To understand the effect of adding a positive constant $\alpha$ to every edge weight, we analyze MSTs and Shortest Paths separately:

• Minimum Spanning Trees (MSTs): Any spanning tree of a graph with $V$ vertices contains exactly $V - 1$ edges. If we add $\alpha$ to the weight of every edge, the total weight of any spanning tree $T$ increases by exactly $(V - 1)\alpha$. Since this is a constant addition for all spanning trees, the relative ordering of their weights remains unchanged. Thus, every MST remains an MST.
• Shortest Paths (SPs): Different paths between two vertices can have different numbers of edges. Adding $\alpha$ to each edge penalizes paths with more edges more heavily than paths with fewer edges. For example, consider two paths between $u$ and $v$: $P_1$ with $1$ edge of weight $10$, and $P_2$ with $3$ edges of weight $3$ each (total weight $9$). Initially, $P_2$ is the shortest path. If we add $\alpha = 2$ to each edge, the weight of $P_1$ becomes $12$ and the weight of $P_2$ becomes $15$. Now, $P_1$ becomes the shortest path. Thus, SPs need not remain SPs.

Hence, every MST remains an MST, and SPs need not remain SPs.