The Gateway to Computer Science Excellence
+20 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$
in Algorithms by Active (3.3k points)
edited by | 3.4k views

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.

Option B should be 2n-2...
It seems this question needs small correction.
what will be the case if weight of the edge v(i, j) is | i+j | ?
I think it would be [(n+1)(n+2)/2] - 3.

5 Answers

+29 votes
Best answer
$2(n-1)$ the spanning tree will traverse adjacent edges since they contain the least weight.
by Active (3.3k points)
edited by
MST will be line graph.

MST will be line graph.

Chhotu  pls explain how?


MST will add the edges with minimum weight, Weight of edges = 2|i−j|.

All successive number will have weights of 2. (like 1-2 weight is 2 , 2-3 weight is 2 so on) Hence it will be a line graph of weight 2 (n-1). i.e n-1 edges each of weight 2.

Take for example K4 an try.
Suppose I take 4 vertices as an example. Then the minimum spanning tree is a line graph with 3 edges of weight 2 each.

now both options B and C gives me the correct minimum weight as 6.


To avoid that take a complete graph of $4$ vertices and then you will only get $\mathbf {B}$ as the answer.

+14 votes
None of the options match the Actual answer.

 For connecting every i & i+1 node we have edge of weight 2 ,therefore We get 2*(n-1).

Correct Answer: $B$
by Boss (41.9k points)
edited by
which is equal to 2n-2
+1 vote

Ans is 2n-2

by Junior (737 points)
+1 vote


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.
by Boss (19.2k points)
edited by
0 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). 

by (215 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,343 users