Q39

MSQ2 marks

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

(A)

The edge with the second smallest weight is always part of any minimum spanning tree of $\textit{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 $\textit{G}.$

(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 \setminus S.$ Such an edge will always be part of any minimum spanning tree of $\textit{G}.$

(D)

$\textit{G}$ can have multiple minimum spanning trees.

Loading…