WhatsApp us
IB DP Maths10 Nov 2026

IB Maths AI HL Graph Theory: Adjacency Matrices, Spanning Trees, Chinese Postman and Travelling Salesman, With Worked Examples

A complete guide to graph theory in IB Maths Applications and Interpretation HL: the vocabulary, adjacency matrices and walks, Eulerian and Hamiltonian routes, Kruskal's and Prim's algorithms, the Chinese postman problem and travelling salesman bounds, with fully worked examples.

IB Maths AI HL Graph Theory: Adjacency Matrices, Spanning Trees, Chinese Postman and Travelling Salesman, With Worked Examples

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.

TermMeaning
Vertex, edgeA point, and a connection between two points
DegreeNumber of edges meeting at a vertex (a loop counts twice)
Simple graphNo loops and no multiple edges between the same pair of vertices
Complete graphEvery pair of vertices is joined by exactly one edge
Weighted graphEach edge carries a number such as distance, time or cost
Directed graphEdges have a direction; each vertex has an in-degree and an out-degree
WalkAny sequence of edges, where vertices and edges may repeat
TrailA walk with no repeated edges
PathA walk with no repeated vertices
Circuit / cycleA closed trail / a closed path
TreeA connected graph with no cycles; a tree on n vertices has n − 1 edges
Spanning treeA 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:

PQRS
P0110
Q1011
R1101
S0110

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):

ABCDEF
A–65––12
B6–47––
C54–89–
D–78–310
E––93–2
F12––102–

Kruskal. Edges in order: EF 2, DE 3, BC 4, AC 5, AB 6, BD 7, CD 8, CE 9, DF 10, AF 12.

  1. EF 2: add.
  2. DE 3: add.
  3. BC 4: add.
  4. AC 5: add.
  5. AB 6: reject, because A and B are already connected through C, so it would form the cycle ABC.
  6. 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.

  1. Add up all edge weights.
  2. Find the odd vertices.
  3. If there are none, the graph is Eulerian and the answer is the total weight.
  4. If there are two, add the shortest path between them (those edges are travelled twice).
  5. 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.
PairingShortest pathsTotal
AB + EFAB = 6, EF = 28
AE + BFACE = 14, BDEF = 1226
AF + BEAF = 12, BDE = 1022

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:

HJKLM
H–1291511
J12–81014
K98–137
L151013–9
M111479–

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.
IB maths AI HL graph theoryKruskal and PrimChinese postman problemtravelling salesman problemIB maths tutor Gurgaon

Related guides

Keep exploring this maths topic

IB DP Maths18 Oct 2026

IB Maths AI HL Matrices, Markov Chains and Graph Theory: A Practical Guide

AI HL brings in tools students have rarely met at school – matrices, eigenvalues, Markov chains and graph theory. What each topic involves, how they appear in exam questions, the GDC skills needed, and how to study them.

IB maths AI HLIB maths matricesMarkov chains IBeigenvalues IB maths

By Ajay Vatsyayan

Read guide

IB DP Maths17 Nov 2026

IB Maths AI HL Topics and Syllabus: The Course Grouped Into Four Modelling Strands, With Hours, Papers and a Checklist

The IB Maths Applications and Interpretation HL syllabus grouped into four modelling strands (change over time, data and inference, networks and states, space and motion), with the IB's teaching hours, the three papers, a tick-off checklist and the changes for the course first examined in 2029.

IB maths AI HL topicsIB maths AI HL syllabusAI HL modellingAI HL checklist

By Maths Bodhi Team

Read guide

IB DP Maths10 Jul 2026

IB Maths AI HL vs AI SL: Topics, Papers, Workload and How to Choose

IB Maths Applications and Interpretation at HL and SL compared: teaching hours by topic, the HL-only content, how the papers differ, whether AI SL has calculus, who should take which level, and what changes for students starting DP in August 2027.

IB maths AI HLIB maths AI SLAI HL vs AI SLIB maths applications and interpretation

By Maths Bodhi Team

Read guide

IB DP Maths17 Nov 2026

Is IB Maths AI HL Hard? Five Common Beliefs Checked Against the IB's Own Figures

AI HL has a reputation as the easier HL maths. This guide checks that against the IB's published hours and papers, names the topics that catch students out, separates fixable problems from signs of the wrong course, and explains how to switch and what a first month with a tutor involves.

is IB maths AI HL hardIB maths AI HL difficultyAI HL vs AA HLIB maths AI HL workload

By Maths Bodhi Team

Read guide

IB DP Maths10 Nov 2026

IB Maths AI HL Vectors and Complex Numbers: Scalar and Vector Products, Kinematics and Complex Forms in Context

What IB Maths Applications and Interpretation HL students need on vectors and complex numbers: scalar and vector products, lines and kinematics, the three forms of a complex number and how complex numbers model waves, with four worked examples and a note on the 2029 course change.

IB maths AI HL vectorsIB maths AI HL complex numbersvector productvector kinematics

By Maths Bodhi Team

Read guide

IB DP Maths17 Nov 2026

IB Maths AI HL Matrix Transformations: Rotations, Reflections, Stretches, Enlargements, Composition and the Determinant

In AI HL, a 2 × 2 matrix moves every point of the plane at once. How to build rotation, reflection, stretch and enlargement matrices from scratch, compose them in the right order, read the determinant as an area scale factor and undo a transformation with the inverse, with four checked examples.

IB maths AI HL matricesmatrix transformations IBdeterminant area scale factorAI HL geometry

By Maths Bodhi Team

Read guide