IB Maths AI HL Graph Theory Paper 1 & 2 Kruskal’s algorithm ~8 min read

Minimum Spanning Trees (Kruskal’s Algorithm)

A minimum spanning tree (MST) is the cheapest way to wire up every vertex in a weighted graph — the lowest-cost set of edges that keeps everything connected, with no cycles. Kruskal’s algorithm finds it the easy way: sort all the edges by weight (smallest first), then add them one at a time, skipping any edge that would create a cycle. Stop once you’ve connected all n vertices — that’s exactly n − 1 edges.

📘 What you need to know

Spanning tree: a subgraph that (i) contains every vertex of the original graph, (ii) is connected, and (iii) has no cycles. A spanning tree of an n-vertex graph has exactly n − 1 edges.
Minimum spanning tree (MST): the spanning tree with the smallest total weight. There may be more than one MST (if two edges have the same weight).
Kruskal’s algorithm: sort edges in increasing order of weight, then add them one by one, rejecting any edge that would create a cycle.
Stopping rule: stop once you have n − 1 edges (where n is the number of vertices), or equivalently when every vertex is connected.
Equal weights: if two edges have the same weight you may pick either — the final tree weight is the same, though the edges chosen might differ.
Show working: examiners expect to see the order in which edges were considered and which were rejected, not just the final tree.
Real-world use: laying cables, water pipes, roads, or fibre — anywhere you want to connect a set of locations as cheaply as possible.

What a minimum spanning tree looks like

Imagine you’re a network engineer wiring up six houses. Every possible cable between them has a different cost (longer = more expensive). You want every house connected to every other house (directly or indirectly), but you want to spend as little money as possible. The answer is a minimum spanning tree: pick exactly the right cables so the whole network is connected, but never any “extra” cables that would create a loop.

Two key facts make this easier than it sounds. First, a tree with n vertices always has exactly n − 1 edges — no more, no less. Second, the cheapest tree is built by being greedy: keep grabbing the smallest available edge that doesn’t break the no-cycle rule. That’s Kruskal’s algorithm in one sentence.

The MST (thick teal) connects all 5 vertices using only 4 edges with total weight 14. The greyed-out edges AB, BE, and DE were either rejected (would form cycles) or never reached — Kruskal stops as soon as n − 1 = 4 edges are selected.

Kruskal’s algorithm in symbols edges sorted: e₁ ≤ e₂ ≤ … ≤ e_m ⇒ add e_i if it doesn’t create a cycle ⇒ stop at n − 1 edges total MST weight = sum of the n − 1 chosen edge weights

Spotting cycles quickly

The only tricky part of Kruskal’s is checking whether adding a new edge would create a cycle. The shortcut: an edge creates a cycle if and only if both of its endpoints are already connected (directly or via earlier edges) in your growing tree. A quick visual check — “are these two vertices already in the same connected piece of my tree?” — is enough for any IB exam graph.

Why does “greedy” work? Kruskal’s algorithm proves a beautiful fact: always taking the cheapest valid edge cannot lead you astray. The reason is that any edge you skip in favour of a smaller one could only have made the total worse. Greedy is optimal here — which is unusual in optimisation problems!

🧭 Recipe — Kruskal’s algorithm step by step

List all edges with their weights, sorted in increasing order. Write them out as a column — this is your “shopping list”.
Start an empty tree. Pick the cheapest edge and add it to your tree. Tick it off the list.
Move to the next-cheapest edge. Check: does adding it create a cycle? If yes, reject it (cross it out, but record that you considered it). If no, add it.
Repeat step 3 until your tree has exactly n − 1 edges (n = total number of vertices in the graph).
Total weight = sum of the weights of the chosen edges. Draw the final tree to present your answer.

Worked examples

WE 1

A simple 4-vertex graph

A graph has vertices { A, B, C, D } and weighted edges AB(5), AC(8), AD(10), BC(3), BD(6), CD(4). Use Kruskal’s algorithm to find the MST and state its total weight.

sort edges by weight BC(3), CD(4), AB(5), BD(6), AC(8), AD(10) consider in order BC(3) → add ✓ CD(4) → add ✓ AB(5) → add ✓ (3 edges, n−1 reached) stopping check: 4 vertices ⇒ need 3 edges total weight 3 + 4 + 5 = 12 MST = { BC, CD, AB }; weight = 12 no edges had to be rejected — the three smallest were all valid.

WE 2

A graph where rejection is needed

The graph below has vertices { P, Q, R, S, T } and weighted edges PQ(2), PR(7), QR(3), QS(5), RS(8), RT(4), ST(6). Find the MST using Kruskal’s algorithm, showing all edges considered.

sort edges PQ(2), QR(3), RT(4), QS(5), ST(6), PR(7), RS(8) apply Kruskal’s PQ(2) → add ✓ QR(3) → add ✓ RT(4) → add ✓ QS(5) → add ✓ (4 edges, done) remaining (not needed, would be rejected anyway) ST(6), PR(7), RS(8) — all create cycles total weight 2 + 3 + 4 + 5 = 14 MST = { PQ, QR, RT, QS }; weight = 14 always state the stopping point — n − 1 = 4 edges for 5 vertices.

WE 3

Rejecting a cycle-forming edge

Apply Kruskal’s algorithm to the graph with vertices { A, B, C, D } and weighted edges AB(1), BC(2), CD(3), AC(4), AD(5), BD(6). List edges in the order considered, clearly indicating which were rejected.

sort edges AB(1), BC(2), CD(3), AC(4), AD(5), BD(6) apply Kruskal’s AB(1) → add ✓ (tree: A–B) BC(2) → add ✓ (tree: A–B–C) CD(3) → add ✓ (tree: A–B–C–D) remaining edges would all create cycles AC(4) — A, C already connected AD(5) — A, D already connected BD(6) — B, D already connected total weight 1 + 2 + 3 = 6 MST = { AB, BC, CD }; weight = 6 the MST happens to be a simple path here — that’s allowed; the rule is “no cycles”, not “branched shape”.

WE 4

Equal weights — multiple MSTs

A graph with vertices { A, B, C, D } has edges AB(4), AC(5), AD(5), BC(7), BD(6), CD(4). Find an MST and its weight. Are there other MSTs of the same weight?

sort edges (note two 4s and two 5s) AB(4), CD(4), AC(5), AD(5), BD(6), BC(7) apply Kruskal’s AB(4) → add ✓ CD(4) → add ✓ AC(5) → add ✓ (3 edges, done) stopping point reached at n − 1 = 3 total = 4 + 4 + 5 = 13 One MST = { AB, CD, AC }; weight = 13 alternative: pick AD(5) instead of AC(5) { AB, CD, AD } also has weight 13 ✓ whenever two edges share a weight and either could be picked next, multiple MSTs exist — but the total weight is always the same.

WE 5

Real-world application — cable network

A company is laying fibre-optic cable between six office buildings. The costs (in thousands of dollars) for each possible direct connection are: AB(8), AC(5), AD(10), BC(9), BD(15), BE(7), CE(6), CF(11), DE(4), DF(12), EF(3). Use Kruskal’s algorithm to find the cheapest set of cables that connects every building, and state the minimum cost.

sort by cost (ascending) EF(3), DE(4), AC(5), CE(6), BE(7), AB(8), BC(9), AD(10), CF(11), DF(12), BD(15) apply Kruskal’s, n − 1 = 5 edges needed EF(3) → add ✓ DE(4) → add ✓ AC(5) → add ✓ CE(6) → add ✓ (now A,C,E,F,D linked) BE(7) → add ✓ (B joins, 5 edges, done) total minimum cost 3 + 4 + 5 + 6 + 7 = 25 minimum cost = $25 000 notice how the algorithm finished before considering any of the larger weights (8 and up) — typical for sparse cost graphs.

WE 6

A larger graph with multiple rejections

A graph has 6 vertices { A, B, C, D, E, F } and edges AB(2), AC(9), AD(6), BC(3), BD(8), BE(7), CE(5), CF(4), DE(10), DF(1), EF(11). Apply Kruskal’s algorithm and find the MST, clearly indicating both added and rejected edges.

sort all edges DF(1), AB(2), BC(3), CF(4), CE(5), AD(6), BE(7), BD(8), AC(9), DE(10), EF(11) apply Kruskal’s, need n − 1 = 5 edges DF(1) → add ✓ AB(2) → add ✓ BC(3) → add ✓ CF(4) → add ✓ (now A,B,C,D,F linked) CE(5) would link E in — wait, E is isolated, add ✓ CE(5) → add ✓ (5 edges, done) would-be rejections (if continued) AD(6), BE(7), BD(8), AC(9), DE(10), EF(11) total weight 1 + 2 + 3 + 4 + 5 = 15 MST = { DF, AB, BC, CF, CE }; weight = 15 the five cheapest edges happened to all be valid here — a clean, lucky case. In trickier graphs you’d reject one or two along the way.

💡 Top tips

Always sort first — write the edges out in increasing weight order before you start picking. This is the step examiners look for.
Show rejections explicitly: cross them out or write “rejected — cycle”. Stating only the final tree loses easy method marks.
Count as you go: you need exactly n − 1 edges. If you’ve got fewer, the graph isn’t fully connected; if you’re tempted to add more, you’re about to make a cycle.
Equal-weight edges are fine: either choice leads to a valid MST. Just pick one and continue.
Draw the final MST at the end, even if not explicitly asked — it’s the clearest way to present the answer.

⚠ Common mistakes

Adding too many edges — the MST has exactly n − 1 edges; one more would create a cycle.
Forgetting to check for cycles: the next-smallest edge isn’t always valid — check both endpoints before adding.
Skipping the sorting step: without sorting you can’t apply the “greedy” rule, and you’ll usually pick a non-optimal edge.
Not showing working: the order of edges considered (and which were rejected) is part of the answer, not just the final tree.
Confusing the MST with the shortest path: the MST connects every vertex cheaply; the shortest path links two specific vertices. Different problems, different answers.

Next up — Minimum Spanning Trees (Prim’s Algorithm). Prim’s solves the same problem as Kruskal’s but uses a different strategy: grow the tree one vertex at a time, always reaching out to the nearest unvisited neighbour. The big advantage is that Prim’s also works on weighted adjacency tables, where Kruskal’s needs the graph drawn.

Need help with Graph Theory?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →

IB Demystified is a trusted online learning platform led by certified IB examiners and educators.