Quiz — Minimum Spanning Trees

Split the vertices of a connected undirected graph into two groups. Why is the lightest edge crossing between the groups safe to add to a minimum spanning tree?

Hint

Think about what any spanning tree must do at the split, and what happens if you swap one edge for another.

Because an edge that crosses the split cannot close a cycle

Every spanning tree crosses the split, and swapping its crossing edge for the lightest one never raises the total

Because every graph has exactly one minimum spanning tree

Because it is the lightest edge in the whole graph