GATE 2020 CS Q.49: solution and answer

Official answer: 99Source: Official answer key, GATE 2020 CS (IIT Delhi)

1. A spanning tree on |V| = 100 vertices has exactly 100 - 1 = 99 edges (standard property of trees).

2. Every edge $(v_i,v_j)$ has weight $|i-j|\ge 1$, since $i$ and $j$ are distinct integers.

3. Therefore any spanning tree of $G$ has total weight $\ge 99\times 1=99$ — this is a lower bound on the MST weight.

4. Consider the path $v_1-v_2-v_3-\cdots -v_{100}$. It has exactly 99 edges, one between each pair of consecutive vertices, and each such edge $(v_i,v_{i+1})$ has weight $|i-(i+1)|=1$.

5. This path connects all 100 vertices and, being a simple path, contains no cycle, so it is a valid spanning tree of $G$ with total weight exactly $99\times 1=99$.

6. Since 99 is both a proven lower bound on every spanning tree and is achieved by this explicit spanning tree, the minimum spanning tree weight of $G$ is $99$.