Consider the following graph: Which one of the following is NOT the sequence…

GATE · 2009 · CS

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?

1. A.

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

2. B.

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

3. C.

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

4. D.

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

Attempted by 344 students.