The GATE Grind

GATE 2022 CS – Question 49

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple select

Consider a simple undirected weighted graph $G$, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $G$ is/are TRUE?

  1. The edge with the second smallest weight is always part of any minimum spanning tree of $G$.
  2. 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. Suppose $S\subseteq V$ be such that $S\ne\phi$ and $S\ne V$. Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V\setminus S$. Such an edge will always be part of any minimum spanning tree of $G$.
  4. $G$ can have multiple minimum spanning trees.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) The edge with the second smallest weight is always part of any minimum spanning tree of $G$.; (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$.; (C) Suppose $S\subseteq V$ be such that $S\ne\phi$ and $S\ne V$. Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V\setminus S$. Such an edge will always be part of any minimum spanning tree of $G$.

Explanation

A: two edges cannot form a cycle in a simple graph. B: edges 3 and 4 cannot both be rejected, since that needs a cycle among the three smallest edges plus another cycle using edge 4, which isn't possible in a simple graph. C is the cut property. D is false because distinct weights give a unique MST.