edited by
14,641 views
32 votes
32 votes

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:

  1. $n-1$
  2. $2n-2$
  3. $\begin{pmatrix} n \\ 2 \end{pmatrix}$
  4. $n^2$
edited by

7 Answers

1 votes
1 votes

To solve the above question we can consider a complete graph with 3 vertices. 

The weight of minimum spanning tree of a Complete Graph of 3 vertices will be 4 (2 (edge 1,2)+2 (edge 2,3)). 

The only option satisfying G with n=3 is option B (i.e 2n-2). 

0 votes
0 votes

By drawing two spanning trees for n=3, and n=4. It can be easily seen that pattern of weights is is indicating that the correction option is choice (b) i.e 2n-2

0 votes
0 votes

Recall the definition of Complete Graph , then the solution is straightforward:

Refer the attached file below:

Answer:

Related questions