GATE CS 2024 Set 2 — Question 59

To find the number of distinct Minimum Spanning Trees (MSTs), we can use Kruskal's algorithm logic, considering edges in increasing order of weights.Step 1: Edges with weight 1
Edges: $(a, b)$, $(f, a)$, $(c, d)$, $(d, e)$.
There are 4 such edges. None of them form a cycle among themselves.

• $(a, b)$ and $(f, a)$ connect nodes $\{a, b, f\}$.
• $(c, d)$ and $(d, e)$ connect nodes $\{c, d, e\}$.

Since these edges must be included in any MST (as they are the unique smallest weights connecting these nodes), we include all 4 edges.
Current components: $C_1 = \{a, b, f\}$, $C_2 = \{c, d, e\}$, $C_3 = \{g\}$.Step 2: Edges with weight 2
Edges connecting to $g$: $(a, g), (b, g), (f, g)$ connect $C_1$ to $g$. $(c, g), (d, g), (e, g)$ connect $C_2$ to $g$.
We need to connect the three components $C_1, C_2, C_3$ together. The MST requires $V-1 = 7-1 = 6$ edges. We currently have 4 edges. We need 2 more edges.To connect $C_1$ to $g$, we can choose any one edge from the set $\{(a, g), (b, g), (f, g)\}$. All have weight 2. Since they all connect the same two components ($C_1$ and $g$), any one of them is valid and will not form a cycle with the others if only one is picked.
Number of choices = 3.To connect $C_2$ to $g$, we can choose any one edge from the set $\{(c, g), (d, g), (e, g)\}$. All have weight 2.
Number of choices = 3.By picking one edge from the first set and one from the second set, we connect $C_1-g-C_2$, forming a single connected component containing all vertices. No cycles are formed.Step 3: Edges with weight 3
Edges $(b, c)$ and $(e, f)$ have weight 3. Since the graph is already connected using weights 1 and 2, adding any weight 3 edge would create a cycle. Thus, no weight 3 edges are included.Total Distinct MSTs
Total combinations = (Choices for connecting $C_1$ to $g$) $\times$ (Choices for connecting $C_2$ to $g$)
Total = $3 \times 3 = 9$.