for a weight of the edge (vi,vj) is 2|i-j|

**The weight of MST will be 2(n-1)**

for a weight of the edge (vi,vj) is |i-j|

**The weight of MST will be (n-1)** // for this question, there is a typo.

7,581 views

Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is:

- $n-1$
- $2n-2$
- $\begin{pmatrix} n \\ 2 \end{pmatrix}$
- $n^2$

Best answer

$\underline{\mathbf{Explanation:}}\Rightarrow$

Make a square of $4$ vertices and make it as a complete graph, that is, having $6$ edges.

Now, make the spanning tree. It will be the $3$ adjacent edges and the weight will be $2+2+2=6$.

Now, check the options and substitute $\mathbf {n = 4}$, then only option $\mathbf B$ is satisfied.

$\therefore \mathbf B$ will be the answer.

Search GATE Overflow