Graph theory makes IB Mathematics: Applications and Interpretation HL feel different from school maths. It sits in Topic 3 (Geometry and trigonometry), which gets 46 suggested teaching hours at AI HL, and it is not part of AI SL. The algorithms are procedural, and marks go to clear, well-ordered working.
This guide covers the whole topic with four original worked examples. For one-to-one help, our IB Maths AI HL tutoring works through these algorithms on exam-style networks.
The vocabulary you must know
Examiners use precise words, and many lost marks come from mixing them up.
| Term | Meaning |
|---|---|
| Vertex, edge | A point, and a connection between two points |
| Degree | Number of edges meeting at a vertex (a loop counts twice) |
| Simple graph | No loops and no multiple edges between the same pair of vertices |
| Complete graph | Every pair of vertices is joined by exactly one edge |
| Weighted graph | Each edge carries a number such as distance, time or cost |
| Directed graph | Edges have a direction; each vertex has an in-degree and an out-degree |
| Walk | Any sequence of edges, where vertices and edges may repeat |
| Trail | A walk with no repeated edges |
| Path | A walk with no repeated vertices |
| Circuit / cycle | A closed trail / a closed path |
| Tree | A connected graph with no cycles; a tree on n vertices has n − 1 edges |
| Spanning tree | A subgraph that is a tree and includes every vertex |
A useful check: the sum of the degrees equals twice the number of edges, since each edge adds 1 to the degree at each end. So the number of odd vertices is always even.
Eulerian and Hamiltonian. An Eulerian trail uses every *edge* exactly once; an Eulerian circuit also returns to its start. A connected graph has an Eulerian circuit when every vertex has even degree, and an Eulerian trail (not closed) when exactly two vertices are odd; the trail then starts at one odd vertex and ends at the other. A Hamiltonian path visits every *vertex* exactly once; a Hamiltonian cycle also returns to its start. There is no simple test for Hamiltonian cycles.
Adjacency matrices and walks
The adjacency matrix A has a row and a column for each vertex; the entry in row i, column j is the number of edges joining vertex i to vertex j. For an undirected graph, A is symmetric. The key fact: the entry in row i, column j of A^k is the number of walks of length k from i to j. A weighted adjacency table lists edge weights instead.
Adjacency matrices tie graph theory to the wider matrices topic, including Markov chains, which we cover in our AI HL matrices and Markov chains guide.
Worked example 1: counting walks
A graph has vertices P, Q, R, S and edges PQ, PR, QR, QS, RS. How many walks of length 3 are there from Q to R?
Order the vertices P, Q, R, S. The adjacency matrix is:
| P | Q | R | S | |
|---|---|---|---|---|
| P | 0 | 1 | 1 | 0 |
| Q | 1 | 0 | 1 | 1 |
| R | 1 | 1 | 0 | 1 |
| S | 0 | 1 | 1 | 0 |
Enter A on the GDC and calculate A³. Its rows are (2, 5, 5, 2), (5, 4, 5, 5), (5, 5, 4, 5) and (2, 5, 5, 2). The Q-row, R-column entry is 5.
Check by listing: QPQR, QRPR, QRQR, QRSR, QSQR. Five walks, matching the matrix; listing small cases catches a mis-entered matrix.
Minimum spanning trees: Kruskal and Prim
A minimum spanning tree (MST) connects every vertex at the lowest total weight, for example the cheapest way to lay cable between buildings.
- Kruskal's algorithm: list edges in increasing order of weight. Add the next edge unless it forms a cycle. Stop when you have n − 1 edges.
- Prim's algorithm: start from any vertex. At each step add the lowest-weight edge joining a vertex already in the tree to one that is not.
- Prim's in matrix form: cross out the row of the starting vertex and number its column. Look down all numbered columns for the smallest uncrossed entry; that entry's row is the next vertex. Cross out its row, number its column, and repeat.
Worked example 2: Kruskal and Prim on the same network
Six villages A to F are linked by possible fibre routes (lengths in km):
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | – | 6 | 5 | – | – | 12 |
| B | 6 | – | 4 | 7 | – | – |
| C | 5 | 4 | – | 8 | 9 | – |
| D | – | 7 | 8 | – | 3 | 10 |
| E | – | – | 9 | 3 | – | 2 |
| F | 12 | – | – | 10 | 2 | – |
Kruskal. Edges in order: EF 2, DE 3, BC 4, AC 5, AB 6, BD 7, CD 8, CE 9, DF 10, AF 12.
- EF 2: add.
- DE 3: add.
- BC 4: add.
- AC 5: add.
- AB 6: reject, because A and B are already connected through C, so it would form the cycle ABC.
- BD 7: add. That is 5 edges for 6 vertices, so stop.
MST: EF, DE, BC, AC, BD. Total = 2 + 3 + 4 + 5 + 7 = 21 km.
Prim from A (matrix form). Start in column A: smallest entry is 5 (row C), so add AC. Now search columns A and C: smallest uncrossed entry is 4 (BC), so add B. Columns A, B, C: smallest is 7 (BD), so add D. Then DE 3, then EF 2. Same tree, same total of 21 km, as it must be when the edge weights are all different.
In the exam, write the order in which edges are chosen. "Kruskal: EF, DE, BC, AC, (AB rejected), BD" shows the examiner your method; a drawing of the final tree on its own does not.
The Chinese postman problem
The Chinese postman problem asks for the shortest closed route that travels along every edge at least once, for example a road-gritting lorry or a fence inspector.
- Add up all edge weights.
- Find the odd vertices.
- If there are none, the graph is Eulerian and the answer is the total weight.
- If there are two, add the shortest path between them (those edges are travelled twice).
- If there are four, list the three ways to pair them up, find the total of the shortest paths for each pairing, and add the smallest.
Worked example 3: four odd vertices
Use the network from Example 2. An inspector must cover every route and return to the start.
- Total weight: 6 + 5 + 4 + 7 + 8 + 9 + 3 + 10 + 2 + 12 = 66 km.
- Degrees: A 3, B 3, C 4, D 4, E 3, F 3. Odd vertices: A, B, E, F.
| Pairing | Shortest paths | Total |
|---|---|---|
| AB + EF | AB = 6, EF = 2 | 8 |
| AE + BF | ACE = 14, BDEF = 12 | 26 |
| AF + BE | AF = 12, BDE = 10 | 22 |
The smallest pairing is AB + EF, so those two edges are repeated. Shortest route = 66 + 8 = 74 km.
Common follow-up: if the route may start and finish at different vertices, repeat only the shortest single link between two odd vertices (here EF = 2) and start and finish at the other two odd vertices, A and B. The route is then 66 + 2 = 68 km.
The travelling salesman problem
The travelling salesman problem (TSP) asks for the shortest Hamiltonian cycle: visit every vertex and return to the start. There is no quick exact method, so you trap the answer between bounds. First make a table of least distances (the shortest route between every pair of vertices), so that the network behaves like a complete graph.
- Upper bound, nearest neighbour algorithm: from the start, always move to the nearest unvisited vertex, then return to the start. The length of this tour is an upper bound.
- Lower bound, deleted vertex algorithm: delete one vertex. Find an MST of what remains. Add the two shortest edges from the deleted vertex. The result is a lower bound.
Keep the *lowest* upper bound and the *highest* lower bound you find.
Worked example 4: bounds for a delivery round
A van visits five depots H, J, K, L, M. The table of least distances (km) is:
| H | J | K | L | M | |
|---|---|---|---|---|---|
| H | – | 12 | 9 | 15 | 11 |
| J | 12 | – | 8 | 10 | 14 |
| K | 9 | 8 | – | 13 | 7 |
| L | 15 | 10 | 13 | – | 9 |
| M | 11 | 14 | 7 | 9 | – |
Upper bound from H. H to K (9), K to M (7), M to L (9), L to J (10), J back to H (12). Tour H-K-M-L-J-H = 47 km.
Lower bound, deleting H. MST of J, K, L, M: KM 7, JK 8, LM 9, total 24. Two shortest edges from H: HK 9 and HM 11. Lower bound = 24 + 9 + 11 = 44 km.
Lower bound, deleting K. MST of H, J, L, M: LM 9, JL 10, HM 11, total 30. Two shortest edges from K: KM 7 and KJ 8. Lower bound = 30 + 7 + 8 = 45 km.
So 45 ≤ optimal tour length ≤ 47 km. Checking all 12 distinct tours by computer shows the optimal is 47 km, so here the nearest neighbour tour happens to be optimal. The exam asks only for the bounds.
Common mistakes
- Mixing up Euler and Hamilton. Eulerian means every edge; Hamiltonian means every vertex.
- Stopping Kruskal too early or too late. A spanning tree on n vertices always has n − 1 edges.
- Missing a pairing in a four-odd-vertex Chinese postman question. There are always exactly three.
- Using the direct edge when a shorter path exists. In the Example 2 network, D to F is 5 km via E, not the direct 10 km.
- Skipping the table of least distances before the TSP algorithms, or keeping the wrong bound at the end.
Exam technique: Papers 1, 2 and 3
All three AI HL papers require a GDC: use it for matrix powers and arithmetic, but write the algorithms out by hand. Papers 1 and 2 are each 120 minutes for 110 marks, so a short graph question (a degree sequence, a walk count, a quick MST) should take only a few minutes. Paper 3 (60 minutes, 55 marks, two extended problem-solving questions) can build a longer investigation; read every part first, as later parts may reuse an earlier tree or table. In every paper, label the vertex order of each matrix, show the order of edges chosen, and give units. Our HL Paper 3 guide covers that style, and our GDC skills guide covers entering and powering matrices quickly.
Other AI HL topics in this series include differential equations and phase portraits and vectors and complex numbers.
How Maths Bodhi helps
Our tutors have students run each algorithm on fresh networks until the steps are automatic, then add context questions where the hard part is building the graph. We mark written working the way an examiner would, looking for method as well as answers. Our IB maths home tutors teach AA and AI at both levels.
Home tuition is available in Gurgaon (Gurugram). Students elsewhere in India and abroad learn with us online. You can book a free demo class.
Frequently asked questions
- Is graph theory in IB Maths AI SL?
- No. Graph theory is additional higher level content, so it is taught in AI HL only.
- What is the difference between Kruskal's and Prim's algorithms?
- Kruskal's adds the cheapest remaining edge that does not form a cycle, while Prim's grows one tree from a starting vertex by adding the cheapest edge to a new vertex; when all weights are different they give the same minimum spanning tree.
- How do you solve the Chinese postman problem with four odd vertices?
- List the three ways of pairing the four odd vertices, add the shortest paths for each pairing, choose the smallest total and add it to the sum of all edge weights.
- How do you find bounds for the travelling salesman problem?
- Use the nearest neighbour algorithm for an upper bound and the deleted vertex algorithm for a lower bound, working from a table of least distances; keep the lowest upper bound and the highest lower bound.
- How do you count walks using an adjacency matrix?
- Raise the adjacency matrix to the power k on your GDC; the entry in row i, column j of A^k is the number of walks of length k from vertex i to vertex j.
- Can I use a calculator for graph theory in IB Maths AI HL?
- Yes. All AI HL papers require a GDC, which is useful for matrix powers and arithmetic, but you still need to write out each step of the algorithms.
