GATE CS 2006 Q11 — Minimum Spanning Trees

To find the weight of the Minimum Spanning Tree (MST) of the complete graph $G$, we analyze the edge weights given by $w(v_i, v_j) = 2|i-j|$.

Since $i \neq j$, the minimum possible difference $|i-j|$ is $1$. Thus, the minimum weight of any edge in the graph is:

Any spanning tree of a graph with $n$ vertices must contain exactly $n-1$ edges. Since the minimum weight of any edge is $2$, the weight of any spanning tree is at least:

We can construct a spanning tree with exactly this weight by selecting the edges between consecutive vertices: $(v_1, v_2), (v_2, v_3), \dots, (v_{n-1}, v_n)$. Each of these $n-1$ edges has a weight of $2|i - (i+1)| = 2$. This forms a path spanning all vertices with a total weight of $2n-2$.

Therefore, the weight of the MST is $2n-2$.