TIFR CSE 2018 | Part B | Question: 3

Question

How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?

• A. $1$
• B. $2$
• C. $4$
• D. $6$
• E. $8$

Comments

option C...... 4

Answer 1

Minimum Weight Spanning Trees of the given graph are

   

$4$ Minimum Weight Spanning Trees each having cost of $14$

Hence, option (C) is the correct answer 

Comments

it should be 4

---

Is there any standard way (any standard formula) to calculate the number of spanning trees in an unweighted undirected graph?

---

There is, but it's very time consuming. It's known as Kirchoff's theorem. You first write down the incidence matrix $B$ of the graph, find its transpose $B^T$, then multiply the two to get the Laplacian matrix $L = B.B^T$.

Then you find the determinant of $L$ and that is the number of MSTs in the graph.

So you are looking at -:

1. Transpose operation.

2. Matrix multiplication operation ($B$ can be quite big if the number of nodes is large).

3. Finding the determinant of a large matrix (if $B$ was large), which means reducing to row echelon form and multiplying diagonal elements.

Easier is to just use combinatorics. As you keep adding edges to your MST, you will find that -:
1. Edges of weight 1 and 2 here must be added - they are non-negotiable, as they are of least weight and adding them does not form a cycle.

2. Edges of weight 3 must not be added - they would form a cycle.

3. Edges of weight 4 and 5 are both two in number and any one must be added - so here you can use counting. 2 choices for each, so $2 * 2 = 4$.

Therefore 4 MSTs.

---

@Ashwani Kumar 2 

How did you write these images what software did you use ? 

BTW your answer was very beautfiul 

Answer 2

option C

$4$ minimum spanning trees are possible

$2$ choices for edges with weight $5$ (any one can be chosen)

$2$ choices for edges with weight $4$ (any one can be chosen)