GATE 2024 CS (CS2) – Question 59
The number of distinct minimum-weight spanning trees of the following graph is _________ (Vertices a,b,c,d,e,f,g; edges: a-b 1, a-f 1, c-d 1, d-e 1, a-g 2, b-g 2, c-g 2, d-g 2, e-g 2, f-g 2, b-c 3, f-e 3.)

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 9
Explanation
Total vertices $=7$ so an MST has 6 edges.
**Weight-1 edges** (a–b, a–f, c–d, d–e) form no cycle, so all four are in every MST. They create components $X=\{a,b,f\}$, $Y=\{c,d,e\}$ and the singleton $\{g\}$.
We need 2 more edges to connect these three components. The cheapest edges between components are weight 2:
- between $g$ and $X$: g–a, g–b, g–f (3 edges)
- between $g$ and $Y$: g–c, g–d, g–e (3 edges)
$X$ and $Y$ are only linked directly by weight-3 edges, which are heavier. So the MST must take exactly one edge from each group: $3\times3=\mathbf{9}$ distinct minimum spanning trees (total weight $4+2+2=8$).
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2023 CS Q56
- GATE 2022 CS Q49
- GATE 2021 CS (CS1) Q27
- GATE 2021 CS (CS1) Q46
- GATE 2021 CS (CS1) Q51
- GATE 2020 CS Q41
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →