Graph Theory (AI HL)
Graph theory models real networks - road systems, delivery routes, social connections - as vertices joined by edges, then applies algorithms to answer practical questions about them. This topic covers building and reading weighted graphs, using adjacency matrices to count walks, finding minimum spanning trees with Kruskal's and Prim's algorithms, and solving route-inspection problems like the Chinese postman problem.
What the syllabus says
Graph theory is AHL-only content, spanning three linked points in the official IB Applications & Interpretation syllabus.
| Code | Syllabus content |
|---|---|
| AHL3.14 | Graphs: vertices, edges, adjacent vertices, adjacent edges, degree of a vertex. Simple, complete, weighted and directed graphs (with in-degree and out-degree). Subgraphs and trees. Knowledge of the terms connected and strongly connected. Students should be able to represent real-world structures - circuits, maps, etc - as graphs. |
| AHL3.15 | Adjacency matrices and weighted adjacency tables. For an adjacency matrix \(A\), the \((i,j)\) entry of \(A^k\) gives the number of walks of length \(k\) connecting vertex \(i\) and vertex \(j\). Construction of the transition matrix for a strongly-connected, undirected or directed graph. |
| AHL3.16 | Walks, trails, paths, circuits and cycles. Eulerian trails and circuits, and how to determine whether one exists. Hamiltonian paths and cycles. Minimum spanning tree algorithms (Kruskal's and Prim's). The Chinese postman problem for a graph with up to four odd vertices. The travelling salesman problem, including nearest neighbour (upper bound) and deleted vertex (lower bound) algorithms. |
Graph theory builds directly on matrices from Topic 1, so expect adjacency-matrix questions to lean on matrix arithmetic skills too.
Key terms
Five words worth knowing cold before you touch the algorithms below - each with a worked example showing exactly what it means.
What is a graph, in graph theory?
A graph is a collection of vertices (points) joined by edges (connections) - it's an abstract model of a network, not a coordinate plot. The number of edges meeting a vertex is its degree, and every edge contributes to the degree of two vertices.
e.g. a graph with 5 edges has degree sum \(2\times5=10\), since each edge adds 1 to the degree of each of its two endpoints.
What is a weighted graph?
A weighted graph attaches a number - distance, cost, time - to each edge, turning an abstract network into a model of a real situation like a road system or delivery route. Algorithms like Kruskal's and Dijkstra's rely on these weights to compare options.
e.g. edges AB, BC, CA of weights 4, 3, 5 give a triangle of total weight \(4+3+5=12\).
What is a minimum spanning tree?
A minimum spanning tree (MST) is the cheapest set of edges that connects every vertex in a network with no cycles. It uses exactly one fewer edge than there are vertices, and Kruskal's and Prim's algorithms both find it, always agreeing on the total weight.
e.g. for a triangle with edges AB 4, BC 3, CA 5, the MST drops the heaviest edge CA, giving weight \(4+3=7\).
What does an adjacency matrix tell you?
An adjacency matrix records which vertices are directly connected, with a 1 (or the edge weight) where two vertices are joined and 0 otherwise. Raising it to a power lets you count walks of a given length between any pair of vertices.
e.g. for the path graph \(1\text{-}2\text{-}3\), \(A^2\) has \((1,1)\) entry \(1\) - exactly one walk of length 2 returns from vertex 1 to itself, via \(1\to2\to1\).
What is the Chinese postman problem?
The Chinese postman problem finds the shortest closed route that travels along every edge of a network at least once, such as a postal round. If a graph has odd-degree vertices, some edges must be repeated to make a closed route (an Eulerian circuit) possible.
e.g. total edge weight 60, with the two odd vertices 8 apart: minimum route \(=60+8=68\).
Key formulas
Graph theory is mostly algorithmic rather than formula-driven - the table below covers the handful of results you do need, and the cards after it walk through each algorithm.
Formula reference
None of these appear as a single named formula in the booklet - graph theory is examined through applying the algorithms correctly, not recalling an equation.
| Result | Used for | Booklet? |
|---|---|---|
| \(\sum \deg(v) = 2|E|\) | Handshaking lemma - checking a degree sequence is valid | Not in booklet |
| \((A^k)_{ij}\) | Number of walks of length \(k\) from vertex \(i\) to vertex \(j\) | Not in booklet - conceptual result |
| MST total weight | Sum of the edges selected by Kruskal's or Prim's algorithm | Not in booklet - algorithm output |
| Chinese postman route | Total edge weight + weight of the repeated shortest path between odd vertices | Not in booklet - algorithm output |
Kruskal's vs Prim's algorithm
Both algorithms always produce a minimum spanning tree of the same total weight - they differ only in how they build it up.
| Feature | Kruskal's algorithm | Prim's algorithm |
|---|---|---|
| Starting point | No fixed start - works through the sorted edge list | Starts at one chosen vertex |
| Selection rule | Add the cheapest edge overall that doesn't create a cycle | Add the cheapest edge joining the tree so far to a new vertex |
| Works well from | A sorted list of edges | A weighted table or matrix |
| Total weight found | Always the minimum | Always the minimum - same as Kruskal's |
Minimum spanning tree algorithms
Both algorithms are examinable and give identical total weights - a question may name a specific one to use.
Kruskal's algorithm
Sort every edge by weight, then add each in turn - cheapest first - skipping any edge that would complete a cycle, until every vertex is connected.
Not in the formula booklet - algorithm to apply by handPrim's algorithm
Start at any vertex. Repeatedly add the cheapest edge that joins a vertex already in the tree to one that isn't, until every vertex is included.
Not in the formula booklet - algorithm to apply by handChecking for cycles
Never add an edge that would connect two vertices already joined (directly or indirectly) by edges you've already chosen - that would create a cycle, which a tree can't contain.
Not in the formula booklet - part of Kruskal's ruleRoute inspection problems
These questions ask how to traverse a network efficiently, rather than how to connect it as cheaply as possible.
Eulerian circuits
A closed route using every edge exactly once (an Eulerian circuit) exists only if every vertex has even degree. If exactly two vertices are odd, an Eulerian trail (not a closed circuit) exists between them.
Not in the formula booklet - existence conditionChinese postman problem
If there are odd vertices, pair them up and repeat the shortest connecting path(s) between each pair to make every degree even, then add that extra distance to the total edge weight.
Not in the formula booklet - algorithmTravelling salesman problem
The nearest neighbour algorithm gives an upper bound for the shortest Hamiltonian cycle; the deleted vertex algorithm gives a lower bound. Neither is guaranteed to find the true minimum.
Not in the formula booklet - bounding algorithmsAdjacency matrices and walks
Matrix powers turn a network diagram into arithmetic you can do on a calculator.
Building the matrix
Row \(i\), column \(j\) records the number of edges directly joining vertex \(i\) to vertex \(j\) (or the weight, in a weighted table) - 0 if there's no edge.
Not in the formula booklet - definitionCounting walks
\[(A^k)_{ij} = \text{number of walks of length } k \text{ from } i \text{ to } j\]
A walk may reuse edges and vertices - it's not the same as a simple path.
Not in the formula booklet - conceptual resultTransition matrices
A transition matrix can be built from a strongly-connected graph's adjacency structure, linking graph theory directly to Markov chains.
Not in the formula booklet - construction methodWorked examples
Two full exam-style questions, marked exactly like the real thing. Try each one yourself before checking the worked solution.
A network connecting towns A-E has edge weights: AB 4, AC 3, BC 2, BD 5, CD 6, CE 7, DE 4.
(a) Use Kruskal's algorithm to find the minimum spanning tree.
(b) State the total weight.
Worked solution
(a) Sort: BC 2, AC 3, AB 4, DE 4, BD 5, CD 6, CE 7. Add cheapest, skipping cycles: BC, AC, (skip AB), DE, BD. M1
MST \(= \{BC, AC, DE, BD\}.\) A1
(b) Total \(= 2 + 3 + 4 + 5 = 14.\) A1
A path graph on 3 vertices (1-2-3) has \(A = \begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}\).
(a) Find \(A^3.\)
(b) State the number of walks of length 3 from vertex 1 to vertex 2.
Worked solution
(a) \(A^2 = \begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}.\) M1
\(A^3 = \begin{pmatrix}0&2&0\\2&0&2\\0&2&0\end{pmatrix}.\) A1
(b) Entry \((1,2)\) of \(A^3\) is \(2\): two walks of length 3. M1 A1
Common mistakes
The four slip-ups that account for most of the marks lost on this topic - worth reading before you start practising, not just after you get one wrong.
- Confusing a minimum spanning tree with a shortest path. An MST minimises the total cost to connect every vertex - it does not give the shortest route between two particular vertices, which is a different problem (solved with Dijkstra's algorithm).
- Forgetting to check for cycles in Kruskal's algorithm. The cheapest remaining edge is only added if it doesn't reconnect two vertices that are already joined by edges you've chosen - skip it and move to the next cheapest if it would.
- Misapplying the Eulerian condition. A closed route using every edge exists only if every vertex has even degree, not just most of them - and the Chinese postman method only handles up to four odd vertices.
- Reading adjacency matrix entries as paths, not walks. \((A^k)_{ij}\) counts walks, which can reuse edges and vertices - it is not the number of simple (non-repeating) routes between the two vertices.
Using your GDC
Kruskal's, Prim's, Dijkstra's and the Chinese postman method are all done by hand - the GDC's role is to total up weights accurately and to handle adjacency-matrix powers. Pick your model to filter down to just the steps that apply to you.
Working out \(A^k\) by hand for anything bigger than a \(3\times3\) matrix is slow and error-prone - let the calculator's matrix mode raise the whole matrix to a power in one step.
- Enter the adjacency matrix \(A\), then compute \(A^k\) directly - do not multiply it out row by row by hand.
- 2nd → MATRX → EDIT to enter [A], then on the home screen type [A]³ (or the required power).TI-84
- Run-Matrix → MAT to enter the matrix, then compute Mat A^3 (or the required power).Casio
- Enter the matrix using the matrix template, then type A^3 (or the required power).Nspire
- Read the required entry from the resulting matrix - row \(i\), column \(j\) gives the number of walks of length \(k\) from vertex \(i\) to vertex \(j\).
Tip: Double-check the matrix dimensions match the number of vertices before raising it to a power - a mistyped entry throws off every walk count.
Kruskal's, Prim's, Dijkstra's and Chinese postman are all applied by hand on paper or on the graph diagram - the calculator's job is just to add the selected weights without an arithmetic slip.
- List the edge weights (or path lengths) your algorithm selected, in the order you chose them.
- Type the sum directly on the home screen, e.g. 2+3+4+5, and press ENTER.TI-84
- Type the sum directly in Run-Matrix and press EXE.Casio
- Type the sum directly on a Calculator page and press enter.Nspire
- Cross-check the total against the number of edges you expect in the answer (a spanning tree always has one fewer edge than there are vertices).
Tip: Keep a running list of which edges you've added as you go - it's easy to double-count or skip one when working from a busy diagram.
See the full GDC guide for more calculator models and topics.
Ready to practise properly?
Graph theory questions, marked instantly like the real exam.
Quick answers
The questions students on this topic ask most often.
What's the difference between a minimum spanning tree and a shortest path?
A minimum spanning tree connects every vertex in a network as cheaply as possible overall. A shortest path (found with Dijkstra's algorithm) only minimises the route between two specific vertices - the two problems can give completely different edge sets.
When can I use Kruskal's algorithm instead of Prim's?
Either always finds a minimum spanning tree and gives the same total weight - they're interchangeable unless the question names one specifically. Kruskal's works from a sorted edge list; Prim's grows outward from a starting vertex, which suits a weighted table better.
What does an entry in A cubed tell you about a graph?
If A is the adjacency matrix of a graph, the (i, j) entry of A cubed gives the number of walks of length 3 from vertex i to vertex j. A walk can reuse edges and vertices, unlike a simple path.
Is graph theory examined at AI SL as well as HL?
No - graph theory (AHL 3.14 to 3.16) is AHL-only content, examined solely on the AI HL papers. Voronoi diagrams are the SL geometry and networks topic instead. See the GDC guide for more calculator-specific instructions.
Sub-topics
Graph Theory broken down into its individual skills, each with its own focused page.
Related topics
More Geometry & Trigonometry topics from the same AI HL syllabus unit, in case you want to keep going.