Graph theory: adjacency matrices, paths and cycles

IB Mathematics Applications and Interpretation HL· Unit 5: Statistics and probability, Topic 12: Graph theory· 15 min read

1. Constructing Adjacency Matrices★☆☆☆☆⏱ 5 min

📘 Definition

Adjacency Matrix

$A$ , $n \times n$ for $n$ vertices

Entry $A_{ij}$ counts the number of edges from vertex $i$ to vertex $j$ . Undirected graphs produce symmetric matrices, directed graphs are often asymmetric.

Example:

A 3-vertex undirected triangle has all off-diagonal entries equal to 1.

Loops (edges that start and end at the same vertex) are recorded on the main diagonal of the matrix. Adjacency matrices are a compact, computer-friendly way to store graph information for further calculations.

📐 Worked Example

Construct the adjacency matrix for the directed graph with vertices $V_{1}, V_{2}, V_{3}$ , with edges: $V_{1} \to V_{2}$ , $V_{1} \to V_{3}$ , $V_{2} \to V_{3}$ , $V_{3} \to V_{1}$ .

1
Confirm the matrix will be $3 \times 3$ , with rows for starting vertices and columns for ending vertices.
2
Fill row 1 (from $V_{1}$ ): $A_{11} = 0$ , $A_{12} = 1$ , $A_{13} = 1$
3
Fill row 2 (from $V_{2}$ ): $A_{21} = 0$ , $A_{22} = 0$ , $A_{23} = 1$
4
Fill row 3 (from $V_{3}$ ): $A_{31} = 1$ , $A_{32} = 0$ , $A_{33} = 0$
5
Final adjacency matrix:
6
$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

2. Counting Paths with Matrix Powers★★★☆☆⏱ 8 min

The core property of adjacency matrices is: the $(i, j)$ entry of $A^{k}$ (the $k$ -th power of $A$ ) equals the number of distinct paths of exactly $k$ edges between vertex $i$ and vertex $j$ . This holds for both directed and undirected graphs.

📐 Worked Example

For the adjacency matrix from the previous example, how many paths of length 2 are there from $V_{1}$ to $V_{3}$ ?

1
Calculate $A^{2} = A \times A$ :
2
$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$
3
The entry for start at $V_{1}$ (row 1) and end at $V_{3}$ (column 3) is 1.
4
There is exactly 1 path of length 2 from $V_{1}$ to $V_{3}$ : $V_{1} \to V_{2} \to V_{3}$ .

✓ Quick check

Test your understanding of convention:

What does the $(2, 1)$ entry in $A^{2}$ represent?
- Number of paths of length 2 from $V_{1}$ to $V_{2}$
- Number of paths of length 2 from $V_{2}$ to $V_{1}$
- Number of cycles of length 2 starting at $V_{2}$
Reveal answer
Number of paths of length 2 from $V_2$ to $V_1$ —
Rows always correspond to starting vertices, columns to ending vertices, so entry $(i, j)$ counts paths from $i$ to $j$ .

3. Identifying Cycles with Adjacency Matrices★★★☆☆⏱ 6 min

A cycle is a path that starts and ends at the same vertex, so all cycles of length $k$ are counted on the main diagonal of $A^{k}$ . The sum of the main diagonal entries is called the trace of $A^{k}$ , and gives the total number of cycles of length $k$ in the entire graph.

📘 Definition

Trace of a Matrix

The sum of all entries on the main diagonal of a square matrix. For $A^{k}$ , $tr (A^{k})$ equals the total number of cycles of length $k$ in the graph.

📐 Worked Example

Find the total number of cycles of length 2 in the 3-vertex directed graph from earlier.

1
We already have $A^{2}$ with diagonal entries $1, 0, 0$ .
2
Calculate the trace:
3
$\text{tr}(A^2) = 1 + 0 + 0 = 1$
4
There is exactly 1 cycle of length 2: $V_{1} \to V_{3} \to V_{1}$ .

4. Real-World Applications★★☆☆☆⏱ 4 min

Adjacency matrices are used to model networks of all kinds: social connections, transport routes, website links, and supply chains. Counting paths helps answer questions about how information or goods flow through a network.

📐 Worked Example

A social network has 3 users: A, B, C. A follows B and C, B follows C, C follows A. How many ways can a message starting at A reach C after exactly 2 followers?

1
This network matches our example graph: A = $V_{1}$ , B = $V_{2}$ , C = $V_{3}$ .
2
We already know the $(1, 3)$ entry of $A^{2}$ is 1.
3
There is exactly 1 path: A → B → C.

5. Common Pitfalls

Wrong move:

Swapping rows and columns for directed graphs, counting edges from $j$ to $i$ instead of $i$ to $j$ .

Why:

IB uses the convention rows = start, columns = end, reversing this gives all counts wrong.

Correct move:

Always label rows as the starting vertex and columns as the ending vertex when building the matrix.

Wrong move:

Interpreting $(A^{k})_{ij}$ as the number of paths of up to $k$ edges, not exactly $k$ edges.

Why:

Exam questions regularly ask for both specific lengths and cumulative lengths, mixing these up leads to wrong answers.

Correct move:

Use $A^{k}$ for exactly $k$ edges, sum $A^{1}$ to $A^{k}$ for up to $k$ edges.

Wrong move:

Counting loops as zero-length cycles, ignoring them when calculating trace.

Why:

A cycle requires at least one edge, so a loop is a valid cycle of length 1.

Correct move:

Include diagonal entries for loops when counting total cycles of any length.

Wrong move:

Setting $A_{ij} = 1$ for multigraphs, even when there are multiple edges between two vertices.

Why:

Multiple edges create multiple distinct paths, so they must be counted explicitly.

Correct move:

Set $A_{ij}$ equal to the actual number of edges between $i$ and $j$ , not just 0 or 1.

6. Quick Reference Cheatsheet

Concept	Interpretation for Adjacency Matrices
Entry $A_{ij}$	Number of edges / length 1 paths from $i$ to $j$
Entry $(A^{k})_{ij}$	Number of paths of exactly $k$ edges from $i$ to $j$
Entry in $A + A^{2} + ... + A^{k}$	Number of paths of up to $k$ edges from $i$ to $j$
Diagonal entry $(A^{k})_{ii}$	Number of cycles of length $k$ starting/ending at $i$
Trace of $A^{k}$	Total number of cycles of length $k$ in the graph
Undirected graph property	$A = A^{T}$ (adjacency matrix is symmetric)

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2021 · 2
Count paths between towns
2022 · 1
Count cycles in directed graph
2023 · 2
Social network path counting

Going deeper

syllabusIB AI HL Official Graph Theory SyllabusOfficial syllabus reference for this topic

What's Next

Adjacency matrices are the foundation for all advanced graph theory problems you will encounter in IB AI HL, including shortest path algorithms, connected component analysis, and network optimization. Counting paths and cycles is regularly tested in both Paper 1 (small non-calculator matrices) and Paper 2 (larger calculator-assisted problems), so mastering this convention and matrix multiplication is key to scoring full marks. Beyond the exam, adjacency matrices are core tools in computer science, network analysis, operations research, and data science for modeling all kinds of connected systems.