Graph Algorithms

One or more correct

• AThe edge with the second smallest weight is always part of any minimum spanning tree of $G$.
• BOne or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of $G$.
• CSuppose $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$.
• D$G$ can have multiple minimum spanning trees.

Answer key coming soon