Spanning trees: Kruskal & Prim
A spanning tree connects all vertices with no cycles, using exactly n − 1 edges; a minimum spanning tree does it at least total weight. Kruskal sorts all edges and adds each unless it forms a cycle; Prim grows one tree, always taking the cheapest edge leaving it. Both are greedy and both are provably optimal, which is unusual and worth noticing.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Kruskal — sort then addSort edges by weight ascending. Add an edge if its endpoints are in different components; skip it otherwise. Stop at n − 1 edges.
- Track componentsUnion-find (or just noting which vertices are joined) is what makes the cycle test quick.
- Prim — grow from a rootStart at any vertex. Repeatedly add the cheapest edge with exactly one endpoint inside the tree.
- Break ties consistentlyDifferent tie-breaking gives different MSTs of the same total weight. State your rule.
Worked example
Run Kruskal on vertices A–D with edges AB=1, BC=2, AC=3, CD=4, BD=5.
- Sorted: AB(1), BC(2), AC(3), CD(4), BD(5).
- Add AB — components {A,B}, {C}, {D}.
- Add BC — components {A,B,C}, {D}. Next, AC(3) would join A and C, already together: skip.
- Add CD — all four vertices joined, and we have 3 = 4 − 1 edges.
Answer. MST = {AB, BC, CD} with total weight 1 + 2 + 4 = 7.
Where marks get dropped
These are the specific errors that cost credit on spanning trees: kruskal & prim questions — QED's rubric penalises each of them separately.
- Adding an edge that closes a cycle. Every edge must join two currently separate components.
- Stopping before n − 1 edges, leaving the tree disconnected, or continuing past it.
- Assuming the MST is unique. With repeated weights several MSTs may exist, all of the same total weight.
Practise this until it is automatic
Unlimited fresh questions
QED generates new spanning trees: kruskal & prim problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.
Spanning trees: Kruskal & Prim — frequently asked questions
Why does the greedy choice work?
The cut property: for any partition of the vertices, the lightest edge crossing it belongs to some MST. Both algorithms only ever add such edges.
Which algorithm is faster?
Kruskal is O(E log E) dominated by sorting, and suits sparse graphs. Prim with a binary heap is O(E log V), and with a Fibonacci heap O(E + V log V), which suits dense graphs.
Is a minimum spanning tree also a shortest-path tree?
No. The MST minimises total weight, not individual distances — Dijkstra’s tree is generally different.
The rest of Graphs
Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Degrees & the handshake lemma
- 2Paths, cycles, connectivity & components
- 3Trees & their properties
- 4Bipartite graphs & colouring basics
- 5Euler & Hamilton paths and circuits
- 6Adjacency matrices & isomorphism
- 7Degree sequences & graphic sequences
- 8Spanning trees: Kruskal & Prim
- 9Shortest paths with Dijkstra
- 10Planarity & Euler’s formula
- 11Directed graphs, in-degree & out-degree
- 12Binary trees: height, traversals & counting
- 13Chromatic number & colouring bounds
- 14Matchings & Hall’s marriage theorem
Ready to make spanning trees: kruskal & prim exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →