Consider the following graph: Which one of the following cannot be the…

PYQ GATE 2006

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

1. A.

   (a—b),(d—f),(b—f),(d—c),(d—e)

2. B.

   (a—b),(d—f),(d—c),(b—f),(d—e)

3. C.

   (d—f),(a—b),(d—c),(b—f),(d—e)

4. D.

   (d—f),(a—b),(b—f),(d—e),(d—c)

Attempted by 522 students.