# Graph theory: adjacency matrices, paths and cycles

> IB Mathematics Applications and Interpretation HL · IB AI HL
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/

This sub-topic covers how to represent graphs as matrices, and use matrix powers to count paths and identify cycles between vertices. You will learn to apply these methods to solve common connection and routing problems in IB exams.

**Prerequisites:** [Matrix operations and powers](https://www.owlsprep.com/study/ib-math-ai-hl-matrix-operations-powers/); [Basic graph theory terminology](https://www.owlsprep.com/study/ib-math-ai-hl-graph-theory-introduction/)

## Learning objectives

- Construct adjacency matrices for directed and undirected graphs
- Calculate the number of paths of a given length between vertices using matrix powers
- Count cycles using trace properties of adjacency matrix powers
- Apply adjacency matrix methods to solve real-world connection problems

## Constructing Adjacency Matrices

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

*Notation:* $A$, $n \times n$ for $n$ vertices

*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}$$

## Counting Paths with Matrix Powers

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.

> **tip**
>
> To find the total number of paths of up to $k$ edges, sum the matrices $A^1 + A^2 + ... + A^k$.

**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$.

**Check your understanding**

Test your understanding of convention:

1. 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$

   *Why:* Rows always correspond to starting vertices, columns to ending vertices, so entry $(i,j)$ counts paths from $i$ to $j$.

## Identifying Cycles with Adjacency Matrices

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.

**Trace of a Matrix** — The sum of all entries on the main diagonal of a square matrix. For $A^k$, $\text{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$.

## Real-World Applications

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.

## Common pitfalls

- **Wrong:** Swapping rows and columns for directed graphs, counting edges from $j$ to $i$ instead of $i$ to $j$.
  - Why it fails: IB uses the convention rows = start, columns = end, reversing this gives all counts wrong.
  - Correct: Always label rows as the starting vertex and columns as the ending vertex when building the matrix.
- **Wrong:** Interpreting $(A^k)_{ij}$ as the number of paths of up to $k$ edges, not exactly $k$ edges.
  - Why it fails: Exam questions regularly ask for both specific lengths and cumulative lengths, mixing these up leads to wrong answers.
  - Correct: Use $A^k$ for exactly $k$ edges, sum $A^1$ to $A^k$ for up to $k$ edges.
- **Wrong:** Counting loops as zero-length cycles, ignoring them when calculating trace.
  - Why it fails: A cycle requires at least one edge, so a loop is a valid cycle of length 1.
  - Correct: Include diagonal entries for loops when counting total cycles of any length.
- **Wrong:** Setting $A_{ij} = 1$ for multigraphs, even when there are multiple edges between two vertices.
  - Why it fails: Multiple edges create multiple distinct paths, so they must be counted explicitly.
  - Correct: Set $A_{ij}$ equal to the actual number of edges between $i$ and $j$, not just 0 or 1.

## 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) |

## 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.

- [Spanning trees and minimum spanning tree algorithms](https://www.owlsprep.com/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/)
- [Graph theory applications: CPP and TSP](https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/