GATE CS 2020 Q49 — Minimum Spanning Trees

We are given a graph $G = (V, E)$ with $100$ vertices, $V = \{v_1, v_2, \dots, v_{100}\}$.

The weight of the edge between any two vertices $v_i$ and $v_j$ is given by $w(v_i, v_j) = |i - j|$.

1. Number of Edges in a Spanning Tree

Any spanning tree of a graph with $n$ vertices must contain exactly $n - 1$ edges. Here, $n = 100$, so any spanning tree of $G$ must have exactly $99$ edges.

2. Minimum Edge Weight

Since $i \neq j$ for any edge, the minimum possible weight of any edge in the graph is:

Therefore, the weight of any spanning tree must be at least $99 \times 1 = 99$.

3. Constructing the Minimum Spanning Tree (MST)

We can construct a spanning tree by connecting consecutive vertices in a path:

The edges in this path are:

The weight of each such edge $(v_i, v_{i+1})$ is:

Since this set of $99$ edges connects all $100$ vertices without forming any cycles, it is a valid spanning tree. The total weight of this spanning tree is:

Since $99$ is the absolute lower bound for the weight of any spanning tree in this graph, the weight of the minimum spanning tree is 99.