Consider a simple undirected weighted graph G, all of whose edge weights are…

GATE · 2022 · CS · Computer Science & IT

1. A.

   The edge with the second smallest weight is always part of any minimum spanning tree of G .

2. B.

   One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G .

3. C.

   Suppose S $\subseteq$ V be such that S $\neq \phi$ and S $\neq$ V . Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G .

4. D.

   G can have multiple minimum spanning trees.

Attempted by 152 students.