GATE CSE 2024 | Set 2 | Question: 49

Question

The number of distinct minimum-weight spanning trees of the following graph is

Answer 1

Correct Answer:   9

As we know, for the Min-Weight Spanning Tree of given graph, we will have 6 edges as the number of vertices are 7.
We want to find all the possible number of MSTs. So, in all the MSTs, "1" weights will be included making 4 edges. 
Now, for the remaining 2 edges we have 6 choices respectively but these 6 choices will be as 3 choices for one edge and 3 choices for the other edge.

So, we will have 3C1 * 3C1 number of MSTs giving us answer as 3*3 = 9.

Note: 3 won't be included in MSTs because we always look for smallest weights.