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

GATE · 2006 · CSTPSC Computer/IT Posts · 2025 · Senior Informatics Officer · Section D

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 431 students.