GATE 2021 CS (CS1) – Question 27
Consider the following undirected graph (a 3x3 grid of vertices, 12 edges) with edge weights: top row horizontal edges 0.1, 0.1; second row horizontal 0.1, 0.9; bottom row horizontal 0.9, 0.1; left column vertical edges 0.9, 0.1; middle column vertical 0.9, 0.1; right column vertical 0.9, 0.1. The number of minimum-weight spanning trees of the graph is ______.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
Label the grid vertices $a,b,c$ (top row), $d,e,f$ (middle row), $g,h,i$ (bottom row).
**Weight-0.1 edges:** $a$–$b$, $b$–$c$, $d$–$e$, $h$–$i$, $d$–$g$, $e$–$h$, $f$–$i$.
These 7 edges contain no cycle, so Kruskal takes all of them. They form two components:
- $\{a,b,c\}$
- $\{d,e,f,g,h,i\}$ (joined by $d$–$e$, $d$–$g$, $e$–$h$, $h$–$i$, $f$–$i$).
**Connecting them:** a spanning tree on 9 vertices needs 8 edges, so exactly one weight-0.9 edge must join the two components. The weight-0.9 edges crossing between them are $a$–$d$, $b$–$e$ and $c$–$f$. The other 0.9 edges lie inside the big component and would create a cycle.
Any one of the 3 crossing edges gives a minimum spanning tree (total weight $7(0.1)+0.9$), so there are **3** MSTs.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2021 CS (CS1) Q46
- GATE 2021 CS (CS1) Q51
- GATE 2020 CS Q41
- GATE 2020 CS Q50
- GATE 2020 CS Q59
- GATE 2019 CS Q48
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →