Spanning trees and MSTs
Tree vs spanning tree, why cycles are unnecessary, and what a minimum spanning tree optimizes. · 11 min read
Concept
A spanning tree of a connected undirected graph is a subset of edges that connects every vertex and contains no cycle. It is a tree that spans the whole graph. If the graph has V vertices, every spanning tree has exactly V - 1 edges.
A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. If the graph represents cities and road costs, an MST is the cheapest way to connect every city so travel between any two cities is possible, without paying for redundant cycles.
Graph prerequisites
MSTs live in connected, undirected, weighted graphs. Directed edges change the problem. Disconnected graphs do not have one spanning tree; they have a spanning forest at best. Negative weights are allowed for MSTs because we are not measuring path distance, only total selected edge weight.
Why cycles are unnecessary
a cycle gives two ways around— If selected edges contain a cycle, one edge on that cycle is redundant for connectivity.remove the heaviest edge on the cycle— The graph stays connected, because the remaining cycle path still links its endpoints.total weight does not increase— Removing a nonnegative or heaviest edge can only help or tie.repeat until no cycles remain— A cheapest connected solution can always be a tree.
Result: An MST is connected, acyclic, and has V - 1 edges
Interactive visualization: MST simulation: accept or reject edges — step through it frame by frame on this page.
Cut property
A cut splits the vertices into two non-empty groups. An edge crosses the cut if it has one endpoint on each side. The cut property says: if an edge is the lightest edge crossing some cut, then there is an MST that contains that edge.
Cycle property
The cycle property is the matching rejection rule: in any cycle, a strictly heaviest edge cannot belong to an MST. If it were included, removing it keeps the graph connected through the rest of the cycle and lowers the total cost.
Complexity target
MST algorithms usually sort edges or use a priority queue. Kruskal is O(E log E) because it sorts all edges. Prim is O(E log V) with a heap and adjacency lists. Both use O(V + E) space for the graph and algorithm state.
Practice: Valid Spanning Tree (Easy) — Check whether undirected edges connect all n nodes without a cycle.