GATE CS 1995 Q22 — Minimum Spanning Trees

The given graph consists of 5 vertices $\{A, B, C, D, E\}$ with the following weighted edges:

• Weight 1: $(A, B)$, $(B, C)$, $(D, E)$
• Weight 2: $(A, C)$, $(C, D)$, $(C, E)$
• Weight 3: $(B, D)$

To find the number of Minimum Spanning Trees (MSTs), we apply Kruskal's Algorithm:

1. Select edges of weight 1: We choose $(A, B)$, $(B, C)$, and $(D, E)$ as they do not form any cycles. This connects the vertices into two components: $\{A, B, C\}$ and $\{D, E\}$.
2. Select edges of weight 2: Edge $(A, C)$ forms a cycle with $(A, B)$ and $(B, C)$, so it is rejected. To connect the two remaining components, we can choose either edge $(C, D)$ or edge $(C, E)$.

This choice gives exactly 2 distinct minimum spanning trees, both with a total weight of $5$:

• MST 1: $\{(A, B), (B, C), (D, E), (C, D)\}$
• MST 2: $\{(A, B), (B, C), (D, E), (C, E)\}$