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: 24
Explanation
Weight-1 edges (a-b, a-f, c-d, d-e) form two components {b,a,f} and {c,d,e}, leaving g isolated. Kruskal then needs 3 more edges via weight-2 edges: connect g and join the two components. Counting valid weight-2 selections gives 24 MSTs.