IB Maths AI HL Graph Theory Paper 1 & 2 Matrix powers M^k ~8 min read

Walks & Adjacency Matrices

An adjacency matrix turns a graph into a square grid of numbers: row i and column j together record the number of edges from vertex i to vertex j. The real power comes from matrix powers: the entries of M^k count walks of length exactly k between every pair of vertices, and the partial sum S_n = M + M² + … + Mⁿ counts walks of length at most n. With a GDC, every “how many walks” question becomes one matrix multiplication away.

📘 What you need to know

Adjacency matrix M: a square matrix where the entry a_ij is the number of edges from vertex i to vertex j. For a simple graph, every entry is 0 or 1.
Undirected graph: M is symmetric (a_ij = a_ji). A loop counts as 1 when filling the matrix (this is the convention for counting walks).
Directed graph: M may not be symmetric. Row sum at vertex v = out-degree; column sum at v = in-degree. A loop still counts as 1.
Length of a walk: the number of edges it uses (vertices and edges may repeat).
Walks of length k: the (i, j) entry of M^k gives the number of walks of length exactly k from vertex i to vertex j.
Walks of length at most n: compute S_n = M + M² + … + Mⁿ; the (i, j) entry gives all walks from vertex i to vertex j of length 1, 2, …, n combined.
Weighted adjacency table: a related table where each cell stores the weight (cost, time, distance) of the edge instead of an edge count. Used for spanning trees and the travelling salesman problem.

From graph to matrix

The recipe for writing an adjacency matrix is simple: list every vertex along the top (columns) and down the side (rows) in the same order, then fill each cell with the number of edges going from the row vertex to the column vertex. For an undirected graph the matrix comes out symmetric — the edge between A and B contributes a 1 in row A column B and a 1 in row B column A. For a directed graph the direction matters: an arrow from A to B puts a 1 in row A column B only.

A loop at vertex v is recorded as a 1 in the diagonal cell (row v, column v). The IB convention — and the one that makes walk-counting work cleanly — is “loop counts as 1”. If two edges connect the same pair of vertices, the cell contains a 2 instead of a 1 (that’s a multigraph).

A 4-vertex undirected graph and its adjacency matrix. The matrix is symmetric because every undirected edge contributes a 1 to both directions (e.g. edge AC puts a 1 at row A col C and at row C col A).

Adjacency matrix entries a_ij = number of edges from vertex i to vertex j undirected ⇒ M is symmetric; loop ⇒ diagonal entry of 1

Counting walks with matrix powers

Here’s the magic. The (i, j) entry of the adjacency matrix M tells you the number of walks of length 1 from i to j — which is just the number of edges between them. Square the matrix and the entries of M² tell you the number of walks of length 2. Cube it and you get walks of length 3. In general, the (i, j) entry of M^k is the number of walks of length exactly k from vertex i to vertex j. Plug the matrix into your GDC and raise to the right power — the answer is already inside.

If you need all walks up to length n (length 1, or 2, …, or n), add the powers together:

The two walk-counting formulas walks of length k: entry of M^k · walks of length at most n: entry of S_n = M + M² + … + Mⁿ read the (i, j) entry: row i, column j

Why does it work? When you multiply M by itself, the (i, j) entry of M² sums up products a_ik·a_kj over all k. Each product is 1 only if there’s an edge from i to k and an edge from k to j — i.e. a 2-step route through some middle vertex k. So the total count is the number of 2-edge walks from i to j.

Weighted adjacency tables

A weighted adjacency table looks similar to an adjacency matrix, but each cell stores the weight (distance, cost, time, probability) of the edge between two vertices rather than the number of edges. An empty cell — usually shown as a dash – means no direct edge exists. Weighted tables are the starting point for everything else in this chapter: minimum spanning trees (Kruskal’s and Prim’s algorithms), upper and lower bounds for the travelling salesman problem, and transition matrices when weights are probabilities.

	A	B	C	D
A	–	12	25	–
B	12	–	14	20
C	25	14	–	9
D	–	20	9	–

A weighted adjacency table — e.g. travel times between four towns. The “–” between A and D means there is no direct road.

🧭 Recipe — using adjacency matrices to count walks

Build the matrix: list vertices as row and column headers in the same order. For each edge, place a 1 in the matching cells (1 in both directions if undirected; only the arrow direction if directed). Loops give a 1 on the diagonal.
Verify quickly: undirected graph ⇒ matrix should be symmetric. Row sum = degree (in undirected) or out-degree (in directed).
Enter M into the GDC (matrix mode) and raise it to the required power.
For walks of length exactly k: read the (i, j) entry of M^k.
For walks of length at most n: compute S_n = M + M² + … + Mⁿ on the GDC, then read the (i, j) entry.

Worked examples

WE 1

Adjacency matrix of an undirected graph

A graph G has vertices { A, B, C, D } and edges { AB, AC, BC, BD, CD }. Write down the adjacency matrix M for G with the vertices listed in alphabetical order.

list each edge in both directions AB → row A col B = 1, row B col A = 1 AC → row A col C = 1, row C col A = 1 BC, BD, CD similarly fill remaining cells with 0   A  B  C  D
A 0  1  1  0
B 1  0  1  1
C 1  1  0  1
D 0  1  1  0 M is symmetric ✓ row sums are 2, 3, 3, 2 — the degrees of A, B, C, D respectively.

WE 2

Adjacency matrix of a directed graph with a loop

A directed graph G has vertices { P, Q, R } and directed edges { P→Q, P→R, Q→R, R→P, R→R } (the last is a loop at R). Write down M, then state the in-degree and out-degree of vertex R.

fill cells using arrow direction only P→Q: row P col Q = 1 P→R: row P col R = 1 Q→R: row Q col R = 1 R→P: row R col P = 1 R→R: row R col R = 1 (loop)   P  Q  R
P 0  1  1
Q 0  0  1
R 1  0  1 in/out-degree of R out-degree = row R sum = 1 + 0 + 1 = 2 in-degree = column R sum = 1 + 1 + 1 = 3 out(R) = 2; in(R) = 3 the loop adds 1 to both the in- and out-degree of R, since the arrow leaves and re-enters the same vertex.

WE 3

Walks of length 2 by hand

The graph G has adjacency matrix M shown below. Compute M² and state the number of walks of length 2 from vertex 1 to vertex 3.

M = 0  1  1
1  0  1
1  1  0

M² = M × M (row × column rule) (1,1): 0·0+1·1+1·1 = 2 (1,2): 0·1+1·0+1·1 = 1 (1,3): 0·1+1·1+1·0 = 1 …similarly for the rest M² =
2  1  1
1  2  1
1  1  2 read (1, 3) entry walks of length 2 from 1 to 3 = 1 the only 2-edge route is 1 → 2 → 3 (going via vertex 2). The route 1 → 3 → 3 doesn’t exist (no loop at 3).

WE 4

Walks of length 4 using the GDC

The adjacency matrix of a graph G with vertices { A, B, C, D, E } is

M = 0  1  1  0  1
1  0  0  1  0
1  0  0  1  0
0  1  1  0  1
1  0  0  1  0

Find the number of walks of length 4 from vertex B to vertex E.

enter M into GDC, compute M⁴ M⁴ =
18  0  0 18  0
0 12 12  0 12
0 12 12  0 12
18  0  0 18  0
0 12 12  0 12 read entry: row B, column E walks of length 4 from B to E = 12 always use the GDC for M⁴ and above — by-hand multiplication is slow and error-prone.

WE 5

Walks of length at most 3 — using S_n

Using the same matrix M as in WE 4, find the number of walks of length 3 or less from vertex A to vertex C.

compute S₃ = M + M² + M³ on the GDC S₃ =
3 7 7 3 7
7 2 2 7 2
7 2 2 7 2
3 7 7 3 7
7 2 2 7 2 read entry: row A, column C walks of length ≤ 3 from A to C = 7 this counts all walks of length 1, length 2, and length 3 combined — not just one of them.

WE 6

Reading information from a weighted adjacency table

The table below shows the distance, in km, between four towns connected by direct roads. Use the table to answer the questions.

	P	Q	R	S
P	–	8	15	–
Q	8	–	6	11
R	15	6	–	9
S	–	11	9	–

(a) State the distance of the direct road from Q to S.
(b) State which pair of towns are not directly connected.
(c) Find the shortest route from P to S, and state its total distance.

(a) read cell row Q col S QS = 11 km (b) look for “—” cells P and S are not directly connected (c) routes from P to S via Q: P → Q → S = 8 + 11 = 19 via R: P → R → S = 15 + 9 = 24 via Q then R: P → Q → R → S = 8 + 6 + 9 = 23 shortest = P → Q → S, 19 km always check multi-step routes — sometimes a longer-looking detour beats a “direct” road.

💡 Top tips

Keep vertex ordering consistent: rows and columns must be in the same order — otherwise your matrix is meaningless.
Use the GDC for M^k when k ≥ 3: by-hand multiplication takes forever and risks arithmetic slips. Enter once, raise to any power.
Symmetry as a check: any undirected adjacency matrix must come out symmetric. If it doesn’t, you’ve missed an edge or recorded a directed one by mistake.
Loops add 1 to the diagonal (walk-counting convention) — not 2. The “degree counts a loop twice” rule is for degree, not for matrix entries.
S_n for “at most n“; M^k for “exactly k“. Read the question carefully — the word “exactly” or “at most” decides which to compute.

⚠ Common mistakes

Recording a loop as 2 in the matrix — for walk counting, a loop is 1 on the diagonal.
Misreading the entry: the (i, j) entry sits in row i and column j. Reading row j column i instead is the classic slip on directed graphs.
Forgetting that walks can repeat edges and vertices — that’s why a walk of length 4 can include cycling back through earlier vertices. Don’t confuse with paths, which can’t repeat.
Using M alone for “at most n“: M gives only walks of length 1. For at most n, you need S_n.
Mixing up adjacency matrix with weighted adjacency table: one counts edges, the other stores weights. Different objects, different uses.

Next up — Minimum Spanning Trees (Kruskal’s Algorithm). The weighted adjacency table we met at the end of this page is the input for finding the cheapest way to connect every vertex in a network. Kruskal’s algorithm builds the tree edge by edge in order of increasing weight, refusing any edge that would create a cycle.

Need help with Graph Theory?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →