GATE CS 2009 Q38 — Minimum Spanning Trees

In Kruskal's algorithm, edges are considered and added to the Minimum Spanning Tree (MST) in strictly non-decreasing order of their weights, provided they do not form a cycle.

From the given graph, the weights of the relevant edges are:

• $w(b, e) = 2$
• $w(a, c) = 3$
• $w(e, f) = 3$
• $w(b, c) = 4$
• $w(f, g) = 5$
• $w(c, d) = 6$

Since Kruskal's algorithm must process all edges of weight $3$ before any edge of weight $4$:

• Both $(a, c)$ and $(e, f)$ (each of weight $3$) must be processed and added before $(b, c)$ (weight $4$).

Let's analyze Option D: (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)

Here, the edge $(b, c)$ with weight $4$ is added before the edge $(a, c)$ with weight $3$. This violates the greedy choice property of Kruskal's algorithm. Thus, Option D is NOT a valid sequence.