Skip to content
Marlbridge

Study Guides

IB DP Mathematics: Applications and Interpretation – Graph theory, adjacency matrices and network algorithms (HL) Study Guide

IB DP Maths AI HL graph theory study guide: graph terms, adjacency and transition matrices, MSTs, Chinese postman and TSP, with worked examples.

Level
IB
Topic
Graph theory, adjacency matrices and network algorithms (HL)
Updated

Aligned to International Baccalaureate IB Diploma Programme Mathematics: Applications and Interpretation (DP Mathematics: Applications and Interpretation), First assessments for SL and HL—2021. Official subject brief .

Syllabus page (what it covers and how it is assessed): IB Diploma Programme Mathematics: Applications and Interpretation.

Syllabus points this page covers

DP Mathematics: Applications and Interpretation

  • 3.14 Graph theory: graphs, vertices, edges, degree, simple/complete/weighted/directed graphs, subgraphs and trees (AHL only)
  • 3.15 Adjacency matrices, walks, weighted adjacency tables, transition matrices for strongly-connected graphs (AHL only)
  • 3.16 Tree and cycle algorithms: Kruskal’s and Prim’s MST, Chinese postman and travelling salesman problems (AHL only)

Found an error? Report a correction.

Need help with this topic? Request a free trial class for IB Diploma Programme Mathematics: Applications and Interpretation (DP Mathematics: Applications and Interpretation).

This study guide teaches the graph theory unit of IB Diploma Programme Mathematics: Applications and Interpretation. It is aligned to the IB Mathematics: applications and interpretation guide, first assessment 2021, syllabus sections 3.14–3.16, and all of it is HL only (AHL). It follows the IB guide for first assessment 2021, which remains the examined syllabus until the new course is first assessed in May 2029, so it applies to the May and November 2026, 2027 and 2028 HL sessions.

When you have worked through it, condense it with the graph theory revision notes and test yourself on the graph theory practice questions. The IB DP Maths AI course hub and the printable syllabus checklist show where the unit sits. For the SL geometry content in the same topic, see AI geometry and trigonometry.

What this unit covers

Syllabus section What you must be able to do SL/HL
3.14 Use graph vocabulary; find degrees; recognise simple, complete, weighted and directed graphs, subgraphs and trees; model real structures as graphs; know “connected” and “strongly connected” HL only
3.15 Write adjacency matrices and weighted adjacency tables; count walks of length k (or up to k) with Aᵏ; build the transition matrix of a strongly connected graph (PageRank) HL only
3.16 Define walks, trails, paths, circuits and cycles; decide whether Eulerian trails or circuits exist; Hamiltonian paths and cycles; Kruskal’s and Prim’s algorithms; Chinese postman; travelling salesman bounds HL only

3.14 Graphs and their vocabulary

A graph is a set of vertices joined by edges. Two vertices are adjacent if an edge joins them. Two edges are adjacent if they share a vertex. The degree of a vertex is the number of edges meeting it (a loop counts 2).

Each edge adds 2 to the total degree, so the sum of the degrees is twice the number of edges. It follows that the number of odd vertices is always even.

  • Simple graph: no loops and no multiple edges between the same pair of vertices.
  • Complete graph Kₙ: a simple graph with every pair of its n vertices joined. It has n(n − 1)/2 edges.
  • Weighted graph: each edge carries a number (distance, cost, time).
  • Directed graph: each edge has a direction. A vertex has an in degree (edges arriving) and an out degree (edges leaving).
  • Subgraph: a graph made from some of the vertices and edges of another.
  • Tree: a connected graph with no cycles. A tree with n vertices has n − 1 edges.
  • Connected: there is a route between every pair of vertices. A directed graph is strongly connected if you can travel from every vertex to every other vertex following the arrows.

You should be able to turn a real structure into a graph: towns become vertices and roads become weighted edges; web pages become vertices and links become directed edges.

Worked example 1

A directed graph has edges P→Q, Q→P, Q→R, R→P, R→S and S→Q. Find the in and out degree of each vertex and decide whether the graph is strongly connected.

Vertex   in   out
P        2    1
Q        2    2
R        1    2
S        1    1
Totals   6    6   (= number of edges)

Route P→Q→R→S reaches every vertex from P. From S: S→Q→P, and Q→R. From R: R→P, R→S, then Q from P. From Q: Q→R→S, Q→P. Every vertex can reach every other, so the graph is strongly connected.

Six small graphs: simple, not simple (loop and double edge, loop counts 2 to the degree), complete K5 with 5x4/2 = 10 edges, weighted, directed, and a tree with 6 vertices and 5 edges.
Each type of graph has a distinguishing feature: loops, completeness, weights, arrows or no cycles.
The directed graph with edges P to Q, Q to P, Q to R, R to P, R to S and S to Q. In/out degrees are P 2/1, Q 2/2, R 1/2, S 1/1; totals are 6 and 6, equal to the number of edges. The numbered walk P, Q, R, S, Q, P visits every vertex and returns, so the graph is strongly connected.
Total in degree equals total out degree equals the number of edges; a closed walk through every vertex shows strong connection.

3.15 Adjacency matrices, walks and transition matrices

The adjacency matrix A has entry aᵢⱼ equal to the number of edges from vertex i to vertex j. For an undirected graph A is symmetric. For a directed graph, row sums give out degrees and column sums give in degrees.

A walk is any sequence of edges where each starts where the last ended. The key result from the guide:

The (i, j)th entry of Aᵏ gives the number of walks of length k from i to j.

For walks of length up to k, add the matrices: A + A² + … + Aᵏ.

Worked example 2

An undirected graph has edges AB, AC, BC, BD and CD. Find the number of walks of length 3 from A to D, and of length at most 3.

      A B C D                   A B C D
A = [ 0 1 1 0 ]          A³ = [ 2 5 5 2 ]
    [ 1 0 1 1 ]               [ 5 4 5 5 ]
    [ 1 1 0 1 ]               [ 5 5 4 5 ]
    [ 0 1 1 0 ]               [ 2 5 5 2 ]

Entry (A, D) of A³ is 2 (A–B–C–D and A–C–B–D). Entries (A, D) of A, A² and A³ are 0, 2 and 2, so there are 4 walks of length at most 3.

A weighted adjacency table holds the edge weights instead of 1s, with a dash where there is no edge. You need one for Prim’s matrix method below.

Transition matrices and PageRank

For a random walk on a strongly connected graph, the transition matrix T has entry Tᵢⱼ = probability of moving from vertex j to vertex i. Each column shares probability equally among the edges leaving that vertex, so every column sums to 1. This matches the Markov chain convention sₙ = Tⁿs₀ (AHL 4.19).

The steady-state vector s satisfies Ts = s with entries summing to 1. In Google’s PageRank idea, pages are vertices, links are directed edges and pages are ranked by their steady-state probabilities.

Worked example 3

Use the directed graph from worked example 1. Out degrees: P 1, Q 2, R 2, S 1.

        from P  Q    R    S
to P   [ 0    1/2  1/2   0 ]
to Q   [ 1     0    0    1 ]
to R   [ 0    1/2   0    0 ]
to S   [ 0     0   1/2   0 ]

Solving Ts = s with p + q + r + s = 1 (or raising T to a high power on your GDC) gives s = (0.3, 0.4, 0.2, 0.1). The ranking is Q, P, R, S.

Graph with edges AB, AC, BC, BD, CD and its adjacency matrix A and A cubed. The (A, D) entry of A cubed is 2, matching the two walks A-B-C-D and A-C-B-D drawn above. Adding the (A, D) entries of A, A squared and A cubed gives 0 + 2 + 2 = 4 walks of length at most 3.
The (i, j) entry of A^k counts walks of length k from i to j.
The directed graph with probabilities on each edge, the transition matrix T (columns are from, rows are to, columns sum to 1) and the steady state s = (0.3, 0.4, 0.2, 0.1) with Ts = s, giving the ranking Q, P, R, S.
Columns of T are probabilities of leaving a vertex; the steady-state vector gives the PageRank ranking.

3.16 Walks, trails, paths and the classical problems

Term Rule
Walk any sequence of adjacent edges
Trail walk with no repeated edge
Path walk with no repeated vertex
Circuit trail that starts and ends at the same vertex
Cycle circuit with no repeated vertex except the start/end

Eulerian trail uses every edge exactly once. Eulerian circuit does so and returns to the start. For a connected graph:

  • all vertices even → an Eulerian circuit exists;
  • exactly two odd vertices → an Eulerian trail exists, starting at one odd vertex and ending at the other;
  • otherwise → neither exists.

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. There is no simple degree test, so you show one exists by writing it down.

Minimum spanning trees

A spanning tree is a subgraph that is a tree and includes every vertex. A minimum spanning tree (MST) has the least total weight.

Kruskal’s algorithm: list edges in increasing weight. Add each edge unless it makes a cycle. Stop at n − 1 edges.

Prim’s algorithm: start at any vertex. Repeatedly add the cheapest edge joining a vertex in the tree to one outside it.

Prim’s matrix method: delete the start vertex’s row and label its column. Find the smallest undeleted entry in the labelled columns; that entry is the next edge and its row is the new vertex. Delete that row, label that column, and repeat.

Worked example 4

Weighted adjacency table:

A B C D E F
A – 7 4 – – –
B 7 – 5 9 – 12
C 4 5 – 8 6 –
D – 9 8 – 3 10
E – – 6 3 – 11
F – 12 – 10 11 –

Kruskal: DE 3 ✓, AC 4 ✓, BC 5 ✓, CE 6 ✓, AB 7 ✗ (cycle A–B–C), CD 8 ✗, BD 9 ✗, DF 10 ✓. Five edges for six vertices, weight 28.

Prim’s matrix method from A: column A gives AC 4. Columns A, C give CB 5. Columns A, B, C give CE 6. Then ED 3, then DF 10. Same tree, weight 28.

Chinese postman problem

Find the shortest closed route that travels along every edge at least once.

  1. Add up all edge weights.
  2. List the odd vertices.
  3. Two odd vertices: add the shortest path between them. Four odd vertices: list the three ways to pair them, find the shortest-path total for each pairing, and add the least.
  4. Route length = total weight + extra.

Why it works: a closed route that uses each edge once needs every vertex to be even, because each visit enters and leaves. Repeating the shortest paths between paired odd vertices makes every degree even at least cost, so an Eulerian circuit then exists.

Worked example 5

Edges: AB 5, AC 8, AD 6, BC 4, BE 7, CD 3, CE 9, DE 10. Total = 52. Degrees: A 3, B 3, C 4, D 3, E 3, so the odd vertices are A, B, D, E.

AB + DE = 5 + 10       = 15
AD + BE = 6 + 7        = 13   ← least
AE + BD = 12 + 7       = 19   (A–B–E, B–C–D)

Repeat AD and BE. Shortest route = 52 + 13 = 65.

Travelling salesman problem (TSP)

Find the Hamiltonian cycle of least weight in a weighted complete graph. If the network is not complete, or a direct edge is longer than an indirect route, first complete a table of least distances.

  • Nearest neighbour algorithm (upper bound): from a start vertex, go to the nearest unvisited vertex each time, then return to the start. The total is an upper bound.
  • Deleted vertex algorithm (lower bound): delete one vertex. Find the MST of what remains. Add the two shortest edges from the deleted vertex. The total is a lower bound.

The best interval uses the smallest upper bound and the largest lower bound found.

Worked example 6

Least distances between five towns:

A B C D E
A – 12 9 14 10
B 12 – 8 11 15
C 9 8 – 7 13
D 14 11 7 – 6
E 10 15 13 6 –

Nearest neighbour from A: A–C 9, C–D 7, D–E 6, E–B 15, B–A 12. Upper bound = 49.

Delete A. MST of B, C, D, E: DE 6, CD 7, BC 8 = 21. Two shortest edges from A: 9 and 10. Lower bound = 21 + 19 = 40.

So 40 ≤ optimal length ≤ 49. Starting the nearest neighbour at B gives 43, a better upper bound.

Three connected graphs: a bowtie with no odd vertices has a numbered Eulerian circuit; a house shape with two odd vertices has a numbered Eulerian trail between them; K4 with four odd vertices has neither.
Zero odd vertices gives an Eulerian circuit, two gives an Eulerian trail, more gives neither.
Six-vertex weighted graph with the minimum spanning tree highlighted. Kruskal accepts DE 3, AC 4, BC 5, CE 6, rejects AB 7, CD 8, BD 9 (cycles) and accepts DF 10, giving five edges of total weight 28.
Kruskal takes the cheapest edges that do not close a cycle until it has n - 1 edges.
Weighted graph with total 52 and odd vertices A, B, D, E. The three pairings cost 15, 13 and 19; the least (AD + BE = 13) is repeated, so the shortest closed route is 52 + 13 = 65.
Pair up the odd vertices by the cheapest shortest paths and add that to the total weight.
Nearest neighbour from A gives tour A-C-D-E-B-A of length 49 (upper bound). Deleting A leaves an MST of weight 21 plus the two shortest edges from A (9 and 10) for a lower bound of 40. Starting at B gives a better upper bound of 43, so the shortest tour is between 40 and 43.
The best lower and upper bounds trap the length of the shortest tour.

Using your GDC

A GDC is required on all three HL papers. Use it for matrix powers (Aᵏ, and sums of powers) and for the steady state of a transition matrix, either by a high power of T or by solving the linear system. The algorithms themselves are carried out by hand, and marks go to the order of edges chosen, so write that order down.

Common errors

  • Reading a transition matrix by rows. In the IB convention, columns are “from” and each column sums to 1.
  • Using A³ when the question asks for walks of length at most 3.
  • Stopping Kruskal’s algorithm before n − 1 edges, or adding an edge that closes a cycle.
  • In the Chinese postman problem, adding the direct edge between odd vertices when a shorter indirect path exists.
  • Checking only one pairing when there are four odd vertices; there are always three.
  • Calling a nearest neighbour total the “answer” to the TSP. It is only an upper bound.
  • Forgetting to convert to a table of least distances before running TSP algorithms.

Frequently asked questions

Is graph theory in the IB Maths AI SL syllabus? No. Graph theory, sections 3.14–3.16 of the IB Maths AI guide, is HL only (AHL) and sits in the geometry and trigonometry topic.

Why is the number of odd vertices in a graph always even? Each edge adds 2 to the total degree, so the sum of the degrees is twice the number of edges and must be even. That is only possible if the number of odd vertices is even.

What is a strongly connected graph? A directed graph is strongly connected if you can travel from every vertex to every other vertex by following the arrows. Transition matrices for PageRank-style random walks are built on strongly connected graphs.

How many edges does a tree with n vertices have? A tree with n vertices has n − 1 edges, so a minimum spanning tree of a network with n vertices also has n − 1 edges.

Official syllabus

International Baccalaureate Organization, Diploma Programme, Mathematics: applications and interpretation guide, first assessment 2021 — sections AHL 3.14, 3.15 and 3.16.

Get free revision emails (optional)

Occasional emails with practice questions, worked explanations and links to free resources for the qualification and subjects you choose. No spam, and you can unsubscribe from any email. The free tools on this site never need an email.

Subjects (optional, up to 6)

Choose a qualification to see its subjects.

Related resources

Related articles

Studying this with a teacher

Working through Mathematics: Applications and Interpretation IB?

This page is free and stays free. If you would rather be taught it, Marlbridge runs Mathematics: Applications and Interpretation classes one-to-one, online in your own time zone. The first trial class is free. WhatsApp replies within an hour (8am–11pm Pakistan time, every day); email the same day.

IB Mathematics: Applications and Interpretation teachers at Marlbridge