GATE CS 2015 Set 3 Q.50 (CS Q.40): Minimum Spanning Trees

Let $G$ be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of $G$ is 500. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes _____.

Your answer

Official answer and solution

Official answer: 995
From: Official GATE 2015 answer key

Solution

Use the property that any spanning tree in a graph with V vertices has exactly V - 1 edges, and adding a constant to all edge weights preserves the MST.

In any connected undirected graph with $V$ vertices, every spanning tree contains exactly $V - 1$ edges.
Here, $V = 100$ , so any spanning tree contains exactly $100 - 1 = 99$ edges.

Let $w(e)$ be the original weight of edge $e$ , and let $w'(e) = w(e) + 5$ be the new edge weight.
For any spanning tree $T$ :

\text{weight}'(T) = \sum_{e \in T} w'(e) = \sum_{e \in T} (w(e) + 5) = \sum_{e \in T} w(e) + 99 \times 5 = \text{weight}(T) + 495

Because every spanning tree has its weight increased by the exact same constant ( $495$ ), the tree that minimizes the original weight also minimizes the new weight (Kruskal's/Prim's edge comparison order is invariant under uniform addition).
Therefore, the new minimum spanning tree weight is:

\text{New MST weight} = 500 + 495 = 995

Final answer

995

Common trap

Multiplying the edge increase by the total number of edges in the graph (300 * 5 = 1500) instead of the number of edges in a spanning tree (99 * 5 = 495).

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 50 of 65, printed as CS Q.40
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