GATE CS 2021 Set 1 Q17 — Minimum Spanning Trees

To find the number of Minimum Spanning Trees (MSTs), we can analyze the graph using Kruskal's algorithm by considering edges in increasing order of their weights:

1. Edges of weight 1: There are two edges of weight 1, which are $(a, b)$ and $(c, d)$. Since they do not form a cycle, both must be included in any MST. This leaves us with two connected components: $$\{a, b\} \quad \text{and} \quad \{c, d\}$$
2. Edges of weight 2: There are three edges of weight 2, which are $(a, d)$, $(b, c)$, and $(a, c)$. To connect the two components into a single spanning tree, we must select exactly one of these weight-2 edges.

Choosing any one of the three weight-2 edges connects the graph without creating any cycles, resulting in a spanning tree of total weight $1 + 1 + 2 = 4$.

Thus, the number of minimum-weight spanning trees is exactly 3.