Question

What will be the cost of the Minimum spanning Tree (MST) of such a graph with n nodes

• A. $n^2-n+1$
• B. $\frac{1}{12}(11n^2-5n)$
• C. $2n+1$
• D. $6n-11$

Answer 1

The correct option is A $n^2-n+1$

We observe a pattern in weight of MST being formed:

$Forn=3\Rightarrow (1+2+3)+\left(1\right)$

$Forn=4\Rightarrow (1+2+3+4)+(1+2)$

$Forn=5\Rightarrow (1+2+3+4+5)+(1+2+3)$

$Forn=6\Rightarrow (1+2+3+4+5+6)+(1+2+3+4)$


In general, total weight of MST for n:

$={\sum }_{i=1}^{n}i+{\sum }_{i=1}^{n-2}i$

$=n^2-n+1$