1
Every connected graph has a spanning tree
Remove cycle edges until none remain; connectivity survives because a cycle edge is never a bridge.
Lesson · Graphs and Trees · Trees
Spanning Trees and Minimum Spanning Trees
A spanning tree reaches every vertex with n − 1 edges. When the edges are weighted, Kruskal's greedy algorithm finds the cheapest one, and its optimality is genuinely surprising.
spanning tree: a subgraph that is a tree containing every vertex
exists ⟺ the graph is connected; has n − 1 edges
KRUSKAL take edges in increasing weight, skip any that closes a cycle
greedy is OPTIMAL here — unusually
Cheapest connection
Core ideas
What this lesson establishes
The minimum spanning tree is the rare optimisation problem where the obvious greedy method is provably right.
2
Kruskal is greedy and correct
Take the cheapest edge that does not close a cycle, repeatedly. The cut property is why this cannot go wrong.
3
Greedy is usually wrong
“Greedy Algorithms” in Algorithms and Complexity shows greedy failing on coin change and on the travelling salesman. Minimum spanning trees are the exception, and the reason is structural.
The material
Spanning trees
Existence, the minimum weight problem, and why greed works here.
Definition · Spanning tree
A spanning tree of a connected graph G is a subgraph that is a tree and contains every vertex of G. It has n − 1 edges.
Theorem · Existence
Every connected graph has a spanning tree.
If G is acyclic it is already a tree. Otherwise take any cycle and remove one of its edges; that edge is not a bridge (“Paths and Connectivity”), so the graph stays connected, and the number of edges has decreased.
Repeating terminates, since the edge count strictly decreases, and it ends with a connected acyclic subgraph on all the vertices — a spanning tree.
□
Breadth-first and depth-first search each produce one directly: the tree edges of a search from any vertex form a spanning tree of its component. So the object is available for free from “Breadth-First and Depth-First Search”.
Minimum spanning trees
Definition · Minimum spanning tree
In a weighted connected graph, a minimum spanning tree is a spanning tree of least total weight.
KRUSKAL(G):
sort the edges by increasing weight
T = ∅
for each edge e in order:
if e does not close a cycle in T: add e to T
return T
Theorem · The cut property
Let S be any nonempty proper subset of the vertices. The lightest edge with exactly one end in S belongs to some minimum spanning tree. If it is strictly lightest, it belongs to every one.
Let e be that lightest crossing edge and let T be a minimum spanning tree not containing it. Adding e to T creates exactly one cycle (“Trees”), and that cycle must cross the cut a second time, at some edge f ≠ e.
Swapping f for e keeps the graph spanning and acyclic, and since w(e) ≤ w(f) the total weight does not increase. So the result is also a minimum spanning tree, and it contains e.
□
Kruskal's correctness follows: whenever it adds an edge, that edge is the lightest crossing the cut between the component it is joining and the rest, so the cut property guarantees a minimum spanning tree containing everything chosen so far.
Prim's algorithm is the same theorem used differently: grow a single tree from one vertex, always adding the lightest edge leaving it. It is Dijkstra's shape with a different priority, and it is often faster on dense graphs.
Why greed works here and usually does not
The cut property is a strong structural fact: a locally cheapest choice is provably part of a global optimum. Most optimisation problems have no such property, and greed then fails — sometimes badly. Coin change with denominations {1, 3, 4} is greedy-wrong at 6, and the travelling salesman is greedy-wrong routinely.
The technical name for the structure that makes greed correct is a matroid, and the forests of a graph form one. “Greedy Algorithms” in Algorithms and Complexity discusses greedy algorithms without the theory; what matters here is that "greedy works" is a theorem about this problem, not a general method.
Cost
Kruskal sorts the edges — Θ(|E| log |E|) — and then tests each for a cycle using a union–find structure, at nearly constant cost per test. So the sort dominates. Prim with a heap runs in Θ((n + |E|) log n).
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Building a minimum spanning tree
Sort, then add whatever does not close a cycle.
1
Sort the edges by weight
This is the dominant cost and the only global step in the algorithm.
2
Take each edge in order if it joins two components
Skip it if both ends are already connected — that would close a cycle.
3
Stop at n − 1 edges
Or when the list is exhausted. Fewer than n − 1 means the graph was disconnected and you have a minimum spanning forest.
4
Verify the count and the connectivity
n − 1 edges reaching every vertex. Both are cheap checks and either failing means the input was disconnected.
Spanning trees
Score 0 / 0Choose the answer you can justify.
Kruskal on five vertices
Edges: AB 1, BC 2, CD 3, DE 4, AE 5, AC 6, BD 7.
sorted: AB(1) BC(2) CD(3) DE(4) AE(5) AC(6) BD(7)
AB 1 components {A,B} TAKE
BC 2 joins {A,B} and {C} TAKE
CD 3 joins {A,B,C} and {D} TAKE
DE 4 joins {A,B,C,D} and {E} TAKE
AE 5 A and E already connected skip
AC 6 already connected skip
BD 7 already connected skip
MST = {AB, BC, CD, DE}, 4 = n − 1 edges, total weight 10
Note the algorithm never reconsidered a choice.
Every edge was decided once and never revisited, which is what makes the algorithm greedy — and what makes its correctness surprising. The cut property is the theorem that licenses never looking back.
Common mistakes
1
Assuming greedy works generallyIt works here because of the cut property. “Greedy Algorithms” in Algorithms and Complexity shows greedy failing on a problem that looks no harder.
2
Reading the tree as a shortest-path treeIt minimises the total weight of the tree, not the distance between any pair. In the worked example the tree route A–B–C–D–E weighs 10 while the rejected edge AE weighs 5. Dijkstra's tree and Kruskal's tree optimise different things.
3
Assuming the minimum spanning tree is uniqueIt is unique when all edge weights are distinct. With ties there may be several, all of the same total weight.
Check your understanding
✓
Finish when you can run Kruskal and justify each rejection.
Take a weighted graph on six vertices and run the algorithm, saying for each rejected edge which two vertices were already connected. That justification is the correctness argument in miniature.
Note: Minimum spanning trees are used for network design, clustering (cut the heaviest edges of the tree and the components are the clusters), and as a subroutine in approximation algorithms — including a 2-approximation for the travelling salesman problem.