GATE 2024 CS2 Q.59: solution and answer

Official answer: 9Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. List edge weights: weight 1 — a-b, a-f, c-d, d-e; weight 2 — g-a, g-b, g-c, g-d, g-e, g-f (g joins every other vertex at cost 2); weight 3 — b-c, f-e.

2. The four weight-1 edges a-b, a-f, c-d, d-e form no cycle (they build a star at a covering {a,b,f} and a path at d covering {c,d,e}), so they are a valid forest.

3. Each of these four edges is forced into every MST by the standard MST exchange property: for a tree edge candidate of weight 1, if it were excluded from some MST T, the path joining its endpoints inside T would have to use only edges of weight ≤ 1 (otherwise swapping in the weight-1 edge would strictly improve T). Checking each: no all-weight-1 path exists between a and b, between a and f, between c and d, or between d and e using only the other three weight-1 edges (each attempt dead-ends at a vertex with no further weight-1 edge). Hence a-b, a-f, c-d, d-e belong to every minimum spanning tree.

4. After fixing these 4 edges, the graph has collapsed into 3 components: X = {a,b,f}, Y = {c,d,e}, and the isolated vertex g. A spanning tree needs exactly 2 more edges to merge 3 components into 1, and those 2 edges must connect the components without forming a cycle (i.e. they must together touch all of X, Y, g).

5. Only three edges leave g toward X (a-g, b-g, f-g, each weight 2) and three leave g toward Y (c-g, e-g, d-g, each weight 2); the only edges directly between X and Y are b-c and f-e, each weight 3.

6. Enumerate the ways to pick 2 edges that span all three components: (i) one X-g edge + one Y-g edge → cost 2+2 = 4, and this spans X, g, Y; (ii) one X-g edge + one X-Y edge → cost 2+3 = 5; (iii) one Y-g edge + one X-Y edge → cost 2+3 = 5; using two X-Y edges, or two edges both from X to g (or both from Y to g), never touches all three components, so those are not spanning. The minimum extra cost is 4, achieved only by case (i): one edge from g to X and one edge from g to Y.

7. Total minimum weight = (1+1+1+1) from the four forced edges + 2 + 2 = 8.

8. Count the minimum-weight spanning trees: choose 1 of the 3 edges {a-g, b-g, f-g} to attach g to X, and independently 1 of the 3 edges {c-g, e-g, d-g} to attach g to Y. Each of the 3 × 3 = 9 combinations, together with the 4 forced weight-1 edges, gives a distinct acyclic spanning tree of total weight 8, and no other combination reaches weight 8.

9. Hence the number of distinct minimum-weight spanning trees is 3 \times 3 = 9.