GATE CS 2016 Set 1 Q.24 (CS Q.14): Minimum Spanning Trees

Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
$P$ : Minimum spanning tree of $G$ does not change
$Q$ : Shortest path between any pair of vertices does not change

$P$ only

$Q$ only

Neither $P$ nor $Q$

Both $P$ and $Q$

Official answer and solution

Official answer: A
From: Official GATE 2016 answer key

Solution

Analyze how an additive edge weight transformation affects spanning tree weights versus path weights with differing hop counts.

Let $G = (V, E)$ be a connected undirected graph with $n$ vertices. Suppose every edge weight $w(e)$ is transformed to $w'(e) = w(e) + c$ for a constant $c > 0$ .

Evaluate Statement $P$ (Minimum Spanning Tree):
Every spanning tree of $G$ contains exactly $n - 1$ edges. If $T$ is any spanning tree, its new weight is:

w'(T) = \sum_{e \in T} w'(e) = \sum_{e \in T} (w(e) + c) = w(T) + (n - 1)c

Because the weight of EVERY spanning tree increases by the exact same constant $(n - 1)c$ , the relative ordering of all spanning trees is completely preserved. The tree that minimized $w(T)$ will also minimize $w'(T)$ . Thus, the MST does not change. Statement $P$ is TRUE.

Evaluate Statement $Q$ (Shortest Paths):
Unlike spanning trees, different paths between a pair of vertices $u$ and $v$ can have different numbers of edges (hop counts). If path $P_1$ has 1 edge and path $P_2$ has 3 edges:

$w'(P_1) = w(P_1) + c$
$w'(P_2) = w(P_2) + 3c$
For example, if $w(P_1) = 5$ and $w(P_2) = 1 + 1 + 1 = 3$ , $P_2$ is initially the shortest path ( $3 < 5$ ).
If $c = 3$ , then $w'(P_1) = 5 + 3 = 8$ , while $w'(P_2) = 3 + 3(3) = 12$ . Now $P_1$ is shorter ( $8 < 12$ ).
Thus, the shortest path can change. Statement $Q$ is FALSE.

Therefore, only Statement $P$ is true.

Final answer

Common trap

Assuming that because edge weights are increased monotonically, the shortest path must also remain unchanged, overlooking path length dependence on edge counts.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 24 of 65, printed as CS Q.14
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source