Consider a graph G = (V, E), where V = {v_1, v_2, ..., v_100}, E = {(v_i, v_j) | 1 <= i < j <= 100}, and weight of edge (v_i, v_j) is |i - j|. The weight of minimum spanning tree of G is _________

GATE 2020 · Algorithms · Minimum Spanning Tree · medium

Answer: The weight of the minimum spanning tree of G is 99.

1. Identify the minimum-weight edges: The minimum possible edge weight is 1, achieved by edges (v_i, v_{i+1}) for i = 1, 2, ..., 99. There are exactly 99 such edges.
2. Verify the 99 unit-weight edges form a spanning tree: The edges {(v_1,v_2), (v_2,v_3), ..., (v_99,v_100)} form a Hamiltonian path — a connected acyclic subgraph covering all 100 vertices. This is a valid spanning tree. Its total weight = 99 * 1 = 99. Any spanning tree of 100 nodes has exactly 99 edges. Since each edge has weight >= 1, the minimum possible MST weight is 99. Our path achieves this lower bound, so it IS the MST.