The GATE Grind

GATE 2024 CS (CS2) – Question 59

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

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.)

Diagram for GATE 2024 CS (CS2) question 59

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →