GATE CS 2014 Set 2 Q.62 (CS Q.52): Minimum Spanning Trees

The number of distinct minimum spanning trees for the weighted graph below is _____.

Your answer

Official answer and solution

Solution

Apply Kruskal's algorithm on the weighted graph to determine independent choices of minimum-weight edges.

Graph Structure and Edge Weights:
The graph consists of 9 vertices with edge weights 1 and 2.
Edges with Weight 1:
- There are 6 edges of weight 1 in the graph.
- None of the weight-1 edges form a cycle among themselves; they form a forest of acyclic components.
- By Kruskal's algorithm, all edges of weight 1 must be included in every MST.
Adding Edges of Weight 2:
- To form a spanning tree on 9 vertices, exactly $9 - 1 = 8$ edges are needed.
- Since all 6 edges of weight 1 are included, exactly $8 - 6 = 2$ edges of weight 2 must be selected.
- Analyzing the components to be connected:
  - The left 6-vertex block has 3 independent cycles of weight 2, offering 3 valid choices to connect the left vertices without creating cycles.
  - The right triangle (containing two edges of weight 2 and one edge of weight 1) requires picking exactly 1 of the two weight-2 edges (2 choices).
  - The choices in the left and right subgraphs are independent.
Total Distinct MSTs:
$\text{Total MSTs} = 3 \times 2 = 6.$

Final answer

Common trap

Overlooking that all weight-1 edges are mandatory, or failing to decompose independent cycle choices.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.