GATE CS 2015 Set 3 Q40 — Minimum Spanning Trees

To find the weight of the new minimum spanning tree (MST), we can use the fundamental properties of spanning trees:

1. Number of Edges in an MST: For any connected undirected graph with $V$ vertices, any spanning tree (including the MST) contains exactly $V - 1$ edges. Here, $V = 100$, so the MST contains: $$V - 1 = 100 - 1 = 99 \text{ edges}$$
2. Effect of Uniform Weight Increase: Increasing the weight of every edge in the graph by a constant $c = 5$ preserves the relative order of all edge weights. Consequently, the set of edges that forms the MST remains unchanged.

Since the same $99$ edges are selected for the new MST, and the weight of each of these edges is increased by $5$, the total weight of the new MST is calculated as:

Thus, the weight of the new minimum spanning tree is 995.