IB DP Maths AI · Topic 3 Geometry and trigonometry · AHL 3.14–3.16 · ~8 min read
Graph theory
HL graph theory for Maths AI: vertices, edges and degrees, simple, complete, weighted and directed graphs, Eulerian and Hamiltonian paths, adjacency matrices and counting walks, minimum spanning trees with Kruskal and Prim, the Chinese postman problem and the travelling salesman problem with upper and lower bounds.
Vertices, edges & degreeSimple, complete, weighted & directed graphsTreesEulerian trails & circuitsHamiltonian paths & cyclesAdjacency matrixCounting walksKruskal & Prim
RSby Riyaz Sir
mentorriyaz.in
mentorriyaz.in
No tag = SL and HLHL ONLY HL students onlyFORMULA BOOKLET given in the examM1A1 how marks are awardedhighlight = comes up again and againTest yourself at the end
In 30 seconds
- A graph is a set of vertices joined by edges. The degree of a vertex is the number of edges at it, and the degrees always add up to twice the number of edges.
- Eulerian: uses every edge once. A circuit exists if every degree is even; a trail (start ≠ end) if exactly two degrees are odd. Hamiltonian: visits every vertex once.
- The adjacency matrix A records edges; the entries of Ak count the walks of length k.
- Minimum spanning tree: Kruskal (take the cheapest edge that doesn't make a cycle) or Prim (grow the tree from one vertex). Chinese postman: traverse every edge and return, repeating the cheapest pairing of odd vertices. Travelling salesman: visit every vertex and return, found between a lower and an upper bound.
- This note is HL only and unchanged for 2029.
By the end you can
- Use the vocabulary of graphs: vertices, edges, degree, simple, complete, weighted, directed, connected, trees and cycles. HL
- Decide whether a graph has an Eulerian trail or circuit, and recognise Hamiltonian paths and cycles. HL
- Write adjacency matrices and use powers of them to count walks. HL
- Find minimum spanning trees with Kruskal's and Prim's algorithms. HL
- Solve Chinese postman problems. HL
- Find upper and lower bounds for the travelling salesman problem. HL
1Graph vocabulary HL
| Word | Meaning |
|---|---|
| simple graph | no loops and no multiple edges between the same pair of vertices |
| complete graph Kn | every vertex joined to every other: n(n − 1)2 edges |
| connected | there is a path between every pair of vertices |
| tree | connected with no cycles; a tree on n vertices has n − 1 edges |
| weighted graph | each edge has a number (weight) |
| directed graph | edges have directions (arrows), like one-way streets |
| walk / trail / path | a route; a trail repeats no edge; a path repeats no vertex |
| cycle | a path that returns to its start |
Worked example
Find the degrees of the vertices in the graph above and check the handshaking lemma.
- A 2, B 4, C 4, D 3, E 3 A1
- sum = 16 = 2 × 8 edges ✓ R1
- Eulerian? D and E have odd degree, so there is an Eulerian trail from D to E (or E to D) but no Eulerian circuit.
2Adjacency matrices and walks HL
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 1 | 1 |
| C | 1 | 1 | 0 | 1 | 1 |
| D | 0 | 1 | 1 | 0 | 1 |
| E | 0 | 1 | 1 | 1 | 0 |
- Row A shows A is joined to B and C. An undirected graph has a symmetric matrix; the row sums are the degrees.
Worked example
How many walks of length 2 go from A to D, and how many of length 3 go from A to B?
- compute A2 and A3 on the GDC M1
- (A2)AD = 2 (A–B–D and A–C–D) A1
- (A3)AB = 7 A1
- Directed graphs (and the transition matrix of a random walk, where each column shows the probabilities of moving from a vertex) are used for web page rankings: the long-term probabilities show which pages are visited most.
3Minimum spanning trees HL
Worked example
Use Kruskal's algorithm to find a minimum spanning tree for the graph.
- order: BC 1, AC 2, DE 2, AB 4, BD 5, BE 6, CD 8, CE 10 M1
- accept BC, AC, DE; reject AB (it would make the cycle A–B–C) A1R1
- accept BD: 4 edges for 5 vertices, done. Weight 10 A1
- Prim's algorithm (from a table): start at any vertex; repeatedly add the cheapest edge joining the tree to a new vertex. In matrix form, cross out the row of each new vertex and circle the smallest number in the columns of the tree.
Common mistakeStopping too early or too late. A spanning tree of n vertices has exactly n − 1 edges.
4Chinese postman problem HL
- Method: list the odd vertices; pair them up in every possible way; find the cheapest total of the shortest paths between pairs; repeat those edges. Route length = total weight + extra.
Worked example
A street sweeper must travel every road in the graph and return to its start. Find the length of the shortest route.
- total weight = 38 A1
- odd vertices: D and E; shortest path DE = 2 M1
- 38 + 2 = 40 (repeat DE) A1
Exam tipWith four odd vertices there are three pairings, for example (A, B)(C, D), (A, C)(B, D), (A, D)(B, C). Find all three totals and choose the smallest.
- Starting and finishing at different vertices: keep the two odd vertices you would pair most expensively as the start and end, and pair the rest.
5Travelling salesman problem HL
- Table of least distances first: if an edge is missing or long, replace it by the shortest path. For example, the least distance from A to B is 3 (A–C–B), not the direct 4.
- Upper bound (nearest neighbour): start at a vertex, always go to the nearest unvisited vertex, then return.
- Lower bound (deleted vertex): delete one vertex; find a minimum spanning tree of the rest; add the two shortest edges from the deleted vertex.
Worked example
Find an upper bound from A by nearest neighbour, and a lower bound by deleting A.
- least distances from A: C 2, B 3, D 8, E 9
- nearest neighbour: A–C (2)–B (1)–D (5)–E (2)–A (9) = 19 M1A1
- delete A: MST of B, C, D, E = BC 1 + DE 2 + BD 5 = 8; add the two smallest least distances from A, 2 and 3: 8 + 5 = 13 M1A1
- so 13 ≤ shortest tour ≤ 19 R1
Common mistakeUsing the nearest neighbour answer as "the" answer. It is only an upper bound: a tour of that length exists, but there might be a shorter one.
Linking questionAdjacency and transition matrices use Matrices and eigenvalues; steady states of random walks link to Markov chains (Estimation, Poisson, hypothesis tests and Markov chains). Voronoi diagrams (Trigonometry, 3D geometry and Voronoi diagrams) are a geometric cousin of these network problems.
Idea for your IA / explorationModel a real network (your school's corridors, a metro map, a delivery round) as a weighted graph and solve a Chinese postman or travelling salesman problem, then compare with the route people actually use.
Test yourself — cover the answers first
Quick check
- HL How many edges does K6 have?
- HL How many edges does a tree on 9 vertices have?
- HL A graph has degrees 2, 2, 4, 4. Is there an Eulerian circuit?
- HL What does entry (i, j) of A³ count?
- HL Is nearest neighbour an upper or a lower bound for the TSP?
Exam-style
- HL A graph has odd vertices P, Q, R, S with shortest paths PQ 5, RS 7, PR 6, QS 4, PS 9, QR 3, and total weight 80. Find the length of the shortest Chinese postman route.
- HL Explain why the deleted vertex method gives a lower bound.
Show answers
- 15
- 8
- yes, all degrees are even
- walks of length 3 from vertex i to vertex j
- an upper bound
- (PQ, RS) = 12; (PR, QS) = 10; (PS, QR) = 12
cheapest pairing PR + QS = 10
80 + 10 = 90 - any tour, with one vertex removed, leaves a path through the other vertices, which is a spanning tree, so it weighs at least the MST
the tour also uses two edges at the deleted vertex, at least the two cheapest
so every tour is at least MST + two cheapest edges
Stuck on a question?
Share with a friendAsk Riyaz SirSend it to me on WhatsApp. I read every message.
Want regular help? Send this to your parent →