GATE CS 2006 Q47 — Minimum Spanning Trees

Kruskal's algorithm finds a Minimum Spanning Tree (MST) by processing and adding edges in strictly non-decreasing order of their weights. If multiple edges have the same weight, they can be processed in any arbitrary order.

From the given graph, the weights of the edges included in the MST are:

• $w(a-b) = 2$
• $w(d-f) = 2$
• $w(b-f) = 5$
• $w(d-c) = 5$
• $w(d-e) = 8$

According to Kruskal's algorithm, any valid sequence of edge additions must satisfy the weight order:

This means:

1. The first two edges added must be $(a-b)$ and $(d-f)$ (in any order).
2. The next two edges added must be $(b-f)$ and $(d-c)$ (in any order).
3. The last edge added must be $(d-e)$.

In Option D, the sequence is $(d-f), (a-b), (b-f), (d-e), (d-c)$. Here, $(d-e)$ (weight $8$) is added before $(d-c)$ (weight $5$), which violates the non-decreasing weight requirement of Kruskal's algorithm.