Graph theory — adjacency matrices, spanning trees and route problems (IB Math AI HL)
Updated October 2026
Quick answer: Graph theory in HL AI is about graphs drawn as vertices and edges: the adjacency matrix (the (i, j) entry of Aⁿ counts walks of length n), minimum spanning trees (Kruskal and Prim), Eulerian and Hamiltonian circuits, and route problems such as the Chinese postman problem.
Vertices, edges and the adjacency matrix, where the (i, j) entry of An counts the walks of length n. Then minimum spanning trees with Kruskal and Prim, Eulerian and Hamiltonian circuits, and the Chinese postman problem, each with a worked example.
Practise Graph theory — adjacency matrices, spanning trees and route problems with AI marking
Open the full HL AI engine — every question in this unit is worked through with instant AI-graded feedback on your handwritten workings.
The degree of a vertex is the number of edges that meet it. The sum of all the degrees is twice the number of edges.
Adjacency matrix: entry (i, j) = number of edges from i to j. For an undirected graph it is symmetric; for a directed graph it is not.
Walks of length n from i to j: the (i, j) entry of Aⁿ. Walks of length up to n: the entry of A + A² + … + Aⁿ.
A tree is connected with no cycles and has exactly n − 1 edges for n vertices. A complete graph Kₙ has n(n − 1)/2 edges.
A weighted adjacency table holds the edge weights instead: it is the starting point for Prim's algorithm.
Worked example
A graph has vertices A, B, C and D and edges AB, AC, BC and CD. Write down its adjacency matrix and find the number of walks of length 3 from A to C.
In the order A, B, C, D, the rows of the adjacency matrix are (0 1 1 0), (1 0 1 0), (1 1 0 1), (0 0 1 0).
On the GDC, the (A, C) entry of A³ is 4.
Check by listing: A–B–A–C, A–C–A–C, A–C–B–C and A–C–D–C.
Answer: 4 walks of length 3.
Minimum spanning trees: Kruskal and Prim
Kruskal's algorithm: add edges in order of increasing weight, skipping any that would make a cycle, until you have n − 1 edges. Prim's algorithm: start at one vertex and keep adding the cheapest edge that joins a new vertex to the tree.
A spanning tree joins all n vertices with n − 1 edges and no cycle; a minimum spanning tree has the smallest total weight.
Kruskal: list the edges by weight, smallest first. Add each one unless it makes a cycle. Stop at n − 1 edges.
Prim: start anywhere. At each step add the cheapest edge from a vertex already in the tree to a vertex not yet in it. From a table, cross out the row of each new vertex and look down the columns already chosen.
Write down the order in which you add the edges: the order is the evidence that you used the algorithm.
Both algorithms give the same total weight; the tree itself can differ when weights tie.
Worked example
A weighted graph has vertices A, B, C, D and E and edges AB = 4, AC = 3, AD = 7, BC = 2, BE = 6, CD = 5, CE = 8 and DE = 4. Use Kruskal's algorithm to find a minimum spanning tree and its weight.
In order of weight: BC 2, AC 3, AB 4, DE 4, CD 5, BE 6, AD 7, CE 8.
Add BC (2), then AC (3).
AB (4) would make the cycle A–B–C, so reject it. Add DE (4).
Add CD (5). That is 4 edges for 5 vertices, so stop.
Weight = 2 + 3 + 4 + 5 = 14. (Prim from A adds AC, CB, CD, DE: the same total.)
Answer: Edges BC, AC, DE and CD, total weight 14.
Eulerian and Hamiltonian circuits
An Eulerian circuit uses every edge exactly once and exists in a connected graph when every vertex has even degree; with exactly two odd vertices there is an Eulerian trail instead. A Hamiltonian cycle visits every vertex exactly once, and there is no simple degree test for it.
Eulerian circuit: travels every edge exactly once and returns to the start. A connected graph has one if and only if every vertex has even degree.
Eulerian trail: travels every edge exactly once but ends somewhere else. It exists when exactly two vertices have odd degree; start at one of them and finish at the other.
Hamiltonian cycle: visits every vertex exactly once and returns to the start. To show one exists, write one down; to show none exists, you need an argument.
The complete graph Kₙ has (n − 1)!/2 different Hamiltonian cycles, which is why the travelling salesman problem is solved with bounds rather than by checking every cycle.
Eulerian is about edges; Hamiltonian is about vertices.
Worked example
A connected graph has five vertices with degrees 2, 4, 3, 3 and 2. How many edges does it have? Does it have an Eulerian circuit or an Eulerian trail? How many Hamiltonian cycles does K₅ have?
Sum of degrees = 2 + 4 + 3 + 3 + 2 = 14, so there are 14 ÷ 2 = 7 edges.
Two vertices have odd degree, so there is no Eulerian circuit.
There is an Eulerian trail, starting at one vertex of degree 3 and ending at the other.
K₅ has (5 − 1)!/2 = 12 Hamiltonian cycles.
Answer: 7 edges; an Eulerian trail but no circuit; 12 Hamiltonian cycles in K₅.
The Chinese postman problem
Find the vertices of odd degree. If there are none, the shortest route is the total weight of all the edges. If there are two, add the shortest path between them. If there are four, try all three pairings and add the cheapest.
The route must use every edge at least once and return to the start.
Count the degree of every vertex. A graph with every degree even has an Eulerian circuit, so the route is just the total weight.
Two odd vertices: the edges on the shortest path between them must be travelled twice, so add that path's length.
Four odd vertices: there are three ways to pair them. Find the shortest paths for each pairing and choose the smallest total.
The shortest path between two odd vertices is not always the direct edge: check routes through other vertices.
Worked example
A graph has edges AB = 5, BC = 7, CD = 6, DA = 8 and AC = 13. Find the length of the shortest route that travels along every edge and returns to the start.
Degrees: A = 3, B = 2, C = 3, D = 2. The odd vertices are A and C.
Total weight = 5 + 7 + 6 + 8 + 13 = 39.
Shortest path from A to C: direct 13, A–B–C = 12, A–D–C = 14. So the shortest is A–B–C = 12.
Route length = 39 + 12 = 51, with AB and BC travelled twice.
5 quick questions on graph theory. No sign-in needed.
A graph has vertices A–E and edges AB = 2, BC = 3, AC = 4, BD = 5, BE = 6, CD = 8, DE = 7 (weights). Find the total weight of a minimum spanning tree.
A directed graph on A, B, C, D has adjacency matrix \(\begin{pmatrix}0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0\end{pmatrix}\) (row = from, column = to). How many walks of length 3 go from A to B?
The vertices of a simple graph have degrees 1, 3, 2, 4, 2. Count its edges.
How many edges does the complete graph \(K_{7}\) have?
A graph has edges AB = 4, BC = 6, CD = 3, DA = 5, AC = 7, BE = 2, EC = 5 (weights). Find the length of the shortest route that travels every edge and returns to its start (the Chinese postman problem).
Add up all the edge weights. Then find the odd-degree vertices, pair them so the total of the shortest paths between the pairs is as small as possible, and add that total.
What is the difference between Eulerian and Hamiltonian?
An Eulerian circuit uses every edge exactly once. A Hamiltonian cycle visits every vertex exactly once. A graph can have one, both or neither.
What is the difference between Kruskal's and Prim's algorithm?
Kruskal's picks the cheapest edges anywhere in the graph, skipping any that make a cycle. Prim's grows one tree from a starting vertex, always adding the cheapest edge to a new vertex. Both give a minimum spanning tree of the same weight.
How do you count walks using an adjacency matrix?
Raise the adjacency matrix to the power n on your GDC. The entry in row i, column j is the number of walks of length n from vertex i to vertex j.
Where can I practise graph theory questions?
On the Graph Theory questions page: 86 exam-style HL AI questions with full mark schemes, plus free step-by-step worked examples.
Can I use my calculator for graph theory?
Yes: a GDC is allowed on every HL AI paper, so practise the calculator method as well as the working.