Every graph-theory tool and trap for IB Mathematics Applications & Interpretation HL — adjacency matrices, counting walks with matrix powers, minimum spanning trees (Kruskal & Prim), Dijkstra shortest paths, the Chinese postman problem and travelling-salesman bounds. Hand-built by an IBO-certified Singapore tutor, with a print-ready PDF to download.
Graph theory is the network topic of IB Mathematics Applications & Interpretation HL, and it is AI to the core: a graph is simply a model of a network — roads between towns, cables between servers, connections in a delivery round — stripped down to vertices joined by edges. Once a real situation is drawn as a weighted graph, standard algorithms optimise it: the cheapest network to build, the shortest route to drive, the tour that visits every customer. A calculator is always allowed, so the marks live in choosing the right algorithm and applying it cleanly — sorting edges, tracking labels, reading a matrix power off the GDC — not in abstract proof.
This cheatsheet condenses the whole of AHL 3.14–3.16 — graph terminology and trees, the adjacency matrix, counting walks with matrix powers, minimum spanning trees (Kruskal & Prim), Dijkstra shortest paths, the Chinese postman problem and travelling-salesman bounds — onto one page, and flags the traps that quietly cost method marks. The print-ready PDF is at the bottom, free to download.
§1 — Graph terminology & trees AHL 3.14
A graph is a set of vertices (nodes) joined by edges. Two vertices are adjacent if an edge joins them, and the degree of a vertex is the number of edge-ends meeting it.
Degree:$\deg(v)=$ number of edges at $v$ — a loop counts twice
Simple graph:no loops and no repeated edges; then each edge just links two distinct vertices
Complete graph:$K_n$ joins every pair, so it has $\dfrac{n(n-1)}{2}$ edges and every vertex has degree $n-1$
Weighted graph:each edge carries a number (distance, cost, time) to be minimised
Directed graph:edges have a direction; each vertex has an in-degree and an out-degree
Tree:a connected graph with no cycles; $n$ vertices are joined by exactly $n-1$ edges
NoteLearn the walk vocabulary: a walk is any run of edges (vertices and edges may repeat); a trail repeats no edge; a path repeats no vertex; a cycle is a closed path back to its start. A subgraph is any graph formed from a selection of the vertices and edges.
TrapIn a directed graph "degree" splits into in- and out-degree, and the two need not match. Only for a simple undirected graph is a vertex's degree just its number of neighbours.
§2 — The adjacency matrix AHL 3.15
A graph is stored for the GDC as its adjacency matrix $A$, where entry $A_{ij}$ counts the edges joining vertex $i$ to vertex $j$. Rows and columns follow the same vertex order.
The running example — a weighted graph on five vertices. Hub vertex C has degree 4; the degree sum is 14 = 2 × 7 edges. The same network drives the adjacency matrix, walks, spanning tree and shortest path below.
Ignoring the weights, the graph above has adjacency matrix (order $A,B,C,D,E$):
Degree:$\deg(i)=$ the sum of row $i$ (here $2,3,4,3,2$) — read straight off the matrix
Weighted table:replace each $1$ with the edge's weight to get the weighted adjacency table used by the algorithms below
TrickFor a simple undirected graph $A$ is symmetric with a zero diagonal. That symmetry is a free error-check when you type the matrix into the GDC.
TrapFor a directed graph $A$ is generally not symmetric: $A_{ij}$ (an arrow $i\to j$) can differ from $A_{ji}$. Keep the rows as "from" and the columns as "to".
§3 — The handshake lemma AHL 3.15
Every edge has two ends, and each end adds $1$ to a vertex's degree. Summing over all vertices therefore double-counts the edges:
Handshake lemma:$\displaystyle\sum_i \deg(i)=2E$, where $E$ is the number of edges
Edge count:$E=\tfrac12\displaystyle\sum_i \deg(i)$ — halve the degree sum
For the graph in §2 the degrees are $2,3,4,3,2$, summing to $14=2\times 7$, confirming $E=7$ edges.
TrapThe degree sum is always even. If yours comes out odd you have miscounted — a valid graph can never have an odd total degree.
NoteA neat consequence: the number of odd-degree vertices is always even. Here that pair is $B$ and $D$ — exactly the vertices the Chinese postman (§7) will have to worry about.
§4 — Counting walks with matrix powers AHL 3.15
Raising the adjacency matrix to a power counts routes through the network — a pure GDC task, no path-tracing by hand.
Walks:$(A^k)_{ij}=$ the number of walks of length $k$ from vertex $i$ to vertex $j$
Length 2:$(A^2)_{ij}$ counts the common neighbours of $i$ and $j$; $(A^2)_{ii}=\deg(i)$
so there are $(A^2)_{AD}=2$ walks of length 2 from $A$ to $D$ (via $B$ and via $C$). Cubing on the GDC gives $(A^3)_{AB}=5$ walks of length 3 from $A$ to $B$.
TrickEnter $A$ once, evaluate $A^k$, and read off the single entry in row $i$, column $j$. Sum all the entries of $A^k$ only when the question asks about the whole network.
Trap"Length" means the number of edges, so a walk of length $n$ needs $A^{n}$, not $A^{n-1}$. Walks may revisit vertices and edges — that is why $A\to B\to A\to B$ is a legitimate length-3 walk.
§5 — Minimum spanning tree: Kruskal & Prim AHL 3.16
A minimum spanning tree (MST) connects all $n$ vertices as cheaply as possible: it is a tree ($n-1$ edges, no cycles) of least total weight — the cheapest network that still reaches everywhere. Two algorithms both find it.
Kruskal:sort every edge in ascending weight; add the cheapest edge that does not create a cycle; stop at $n-1$ edges
Prim:start at any vertex; repeatedly add the cheapest edge that joins a new vertex to the tree so far
On the §2 graph, Kruskal takes $DE(2),AC(3),BC(4)$, rejects $AB(5)$ as a cycle, then adds $CD(7)$ to reach all five vertices: MST weight $=2+3+4+7=16$.
TrickBoth algorithms give the same total weight. Kruskal sorts edges globally (best by hand when there are few edges); Prim grows one connected blob outward from a start vertex (best on dense graphs).
TrapNever add an edge whose two ends are already connected — it closes a cycle. Take the next-cheapest instead, and stop the moment you have $n-1$ edges.
§6 — Shortest path: Dijkstra's algorithm AHL 3.16
Where the MST builds the cheapest whole network, Dijkstra's algorithm finds the single cheapest route between two chosen vertices in a weighted graph.
Label:give each vertex a "best distance so far" from the start; the start begins at $0$
Fix & relax:permanently fix the smallest un-fixed label, then update ("relax") each of its neighbours; repeat
From $A$ in the §2 graph the shortest distance to $E$ is $11$, along $A\to C\to E$ ($3+8$) — cheaper than the direct-looking $A\to C\to D\to E=12$.
TrickOnce a vertex holds the smallest un-fixed label it can never improve, so fix it and move on. Back-track the fixed labels at the end to read off the actual route, not just its length.
TrapDijkstra minimises total weight, not the number of edges. A three-edge path can easily beat a one-edge path if that single edge is heavy — always add the weights, never count the hops.
§7 — Chinese postman (route inspection) AHL 3.16
The Chinese postman problem asks for the shortest closed route that travels every edge at least once and returns to the start (think gritting every road, or inspecting every cable).
Eulerian circuit:if every vertex has even degree, such a route reuses no edge — length $=$ total edge weight
Two odd vertices:repeat the shortest path between the odd pair; route $=$ total weight $+$ that shortest distance
The §2 graph has odd vertices $B$ and $D$. The shortest $B$–$D$ path is $B\to C\to D=11$ (not the direct edge, weight $12$), and the edges total $41$, so the postman route is $41+11=52$.
TrapThe repeated distance is the shortest path between the two odd vertices, which may run through another vertex rather than along the direct edge — here $11$ via $C$ beats the direct $12$.
NoteChinese postman is about covering every edge (Eulerian). Contrast the next section, the travelling salesman, which is about visiting every vertex (Hamiltonian) — a completely different problem.
The travelling-salesman problem (TSP) seeks the cheapest tour that visits every vertex exactly once and returns to the start — a Hamiltonian cycle of least weight. There is no quick exact method, so AI HL asks you to trap the answer between two bounds.
Tour count:the complete graph $K_n$ has $\dfrac{(n-1)!}{2}$ distinct Hamiltonian cycles — far too many to check for large $n$
Upper bound:nearest-neighbour — from the start, always go to the closest unvisited vertex, then return to the start
Lower bound:deleted-vertex — delete one vertex, find the MST of what remains, then add the two cheapest edges at the deleted vertex
TrickNearest-neighbour gives a real tour, so it is an upper bound; deleted-vertex gives a lower bound. Together they squeeze the optimum: lower $\le$ optimal $\le$ upper. Trying different start/deleted vertices tightens the squeeze.
TrapTwo classic slips: in nearest-neighbour, don't forget the final leg back to the start — it is part of the tour. In deleted-vertex, the two added edges must both touch the deleted vertex (they need not touch each other).
§9 — Synthesis: random walks & steady state AHL 3.15
Graph theory feeds straight into the Markov-chain toolkit. Let a walker hop from its current vertex to a uniformly random neighbour. The transition matrix reads straight off the graph: from a vertex of degree $d$, each neighbour is reached with probability $\tfrac{1}{d}$.
Transition:from a degree-$d$ vertex, move to each neighbour with probability $\tfrac1d$ (e.g. from $A$, degree $2$: to $B$ or $C$, each $\tfrac12$)
Steady state:$\pi_i=\dfrac{\deg(i)}{2E}=\dfrac{\deg(i)}{\sum_k \deg(k)}$ — the long-run share of time spent at vertex $i$
For the §2 graph, $\pi=\dfrac{1}{14}(2,3,4,3,2)$, so the walker spends $\tfrac{4}{14}=\tfrac27$ of its time at the hub $C$ — the most-connected vertex, as expected.
TrickThe steady state is degree-weighted, not uniform: divide each degree by $2E$ (the sum of all the degrees), not by the number of edges $E$.
NoteFormally the steady state is the eigenvector for eigenvalue $1$ of the transition matrix — the bridge to the AHL 1.15 eigenvalue and Markov-chain topic. Graph theory supplies the degrees; the Markov chain turns them into long-run probabilities.
§10 — Exam attack plan All sections
Question cue
What to do
Watch for
"Degree of a vertex"
Sum its row in $A$ (or count edge-ends)
A loop adds 2; directed $\Rightarrow$ in- vs out-degree
"How many edges?"
Handshake: $E=\tfrac12\sum\deg(i)$
The degree sum must be even
"Walks of length $n$ from $i$ to $j$"
Compute $A^{n}$ on the GDC; read entry $(i,j)$
Power $n$, not $n-1$; walks may repeat vertices
"Cheapest network / spanning tree"
Kruskal (sort edges) or Prim (grow from a vertex)
$n-1$ edges; never close a cycle
"Shortest route between two vertices"
Dijkstra: fix smallest label, relax neighbours
Least weight, not fewest edges
"Travel every road and return"
Chinese postman: total weight $+$ shortest odd-pair path
Repeated path may pass through another vertex
"Shortest tour of every vertex"
TSP: nearest-neighbour (UB) & deleted-vertex (LB)
Include the return leg; two edges at the deleted vertex
"Long-run share of a random walk"
Steady state $\pi_i=\deg(i)/2E$
Degree-weighted; divide by $2E$, not $E$
Worked Example — AI HL-Style Travelling Salesman
Question (AI HL Paper 2 style — 6 marks)
A courier must start at hub $P$, visit hubs $Q$, $R$, $S$, $T$ exactly once, and return to $P$. The distances (km) between hubs are:
P
Q
R
S
T
P
–
9
12
8
15
Q
9
–
7
11
6
R
12
7
–
10
13
S
8
11
10
–
5
T
15
6
13
5
–
(a) Use the nearest-neighbour algorithm from $P$ to find an upper bound for the shortest tour. (b) By deleting vertex $P$, find a lower bound for the shortest tour.
Solution
(a) Nearest-neighbour from $P$: the closest hub to $P$ is $S$ ($8$); from $S$ the closest unvisited is $T$ ($5$); from $T$ it is $Q$ ($6$); from $Q$ only $R$ remains ($7$); finally $R\to P$ ($12$). (M1) Tour $P\to S\to T\to Q\to R\to P$. (A1) Length $=8+5+6+7+12=38$ km, so the shortest tour is at most $\mathbf{38}$ km. (A1)
(b) Delete $P$. On the remaining vertices $\{Q,R,S,T\}$ the minimum spanning tree (Kruskal) takes $ST(5),\,QT(6),\,QR(7)$, of weight $5+6+7=18$. (M1)(A1) Now add the two cheapest edges at $P$: $PS=8$ and $PQ=9$. Lower bound $=18+8+9=35$ km. (A1)
Examiner's note: quote both bounds together — $35\le$ shortest tour $\le 38$ km. Nearest-neighbour gives a genuine tour, so remember its return leg $R\to P$; the deleted-vertex method needs the two smallest edges at the deleted vertex, both incident to it. Different start or deleted vertices legitimately give different bounds — pick the highest lower bound and lowest upper bound to squeeze hardest, and keep the units (km).
Common Student Questions
For walks of length $n$, do I raise the adjacency matrix to the power $n$ or $n-1$?
To the power $n$. A walk of length $n$ uses $n$ edges, and $(A^n)_{ij}$ counts exactly those walks from vertex $i$ to vertex $j$. Enter $A$ on the GDC, compute $A^n$, and read the single entry in row $i$, column $j$ — or sum every entry of $A^n$ for the whole network. Using $n-1$ is the classic off-by-one error here, and remember walks may reuse vertices and edges.
What is the difference between Kruskal's and Prim's algorithms?
They build the same minimum spanning tree with the same total weight — only the bookkeeping differs. Kruskal looks at edges globally: sort them all, then keep adding the cheapest edge that does not make a cycle. Prim grows one connected piece locally: start anywhere and repeatedly add the cheapest edge that reaches a new vertex. Kruskal is usually easier by hand when there are few edges; Prim is tidier on dense graphs.
When does a graph have an Eulerian circuit, and how does the Chinese postman use it?
A connected graph has an Eulerian circuit — a closed route using every edge exactly once — precisely when every vertex has even degree. Then the Chinese postman route is just the total edge weight. If exactly two vertices are odd, you must repeat the shortest path between them, adding that distance to the total. (More than two odd vertices is beyond AI HL.)
Which travelling-salesman method gives the upper bound and which the lower?
The nearest-neighbour algorithm produces an actual tour, so its length is an upper bound (the true optimum is at most this). The deleted-vertex method gives a lower bound (the optimum is at least this). Together they trap the answer: lower $\le$ optimal $\le$ upper. Trying different starting vertices for nearest-neighbour, or deleting different vertices for the lower bound, can tighten the gap.
What is the difference between Eulerian and Hamiltonian — and between a walk, trail and path?
An Eulerian route uses every edge once (the Chinese postman family); a Hamiltonian cycle visits every vertex once (the travelling-salesman family) — edges versus vertices is the whole distinction. As for the route words: a walk allows any repeats, a trail repeats no edge, a path repeats no vertex, and a cycle is a closed path returning to its start.
What's NOT in this cheatsheet
This page gives you the formulas and traps for free. The full Photon Academy IB Math AI HL library (enrolled students, or the lifetime resource library) adds:
Notes PDF — every graph-theory definition, algorithm and worked network in full, with the exact GDC steps for adjacency-matrix powers.
Tutorial booklet — 25+ AI HL-style questions from graph terminology to full spanning-tree, Dijkstra and travelling-salesman applications.
Tutorial Solutions — mark-scheme-style solutions with M1/A1 annotations for every algorithm.
Predicted-paper questions — the exact graph-theory and travelling-salesman question types most likely in the next session.
