IB Mathematics: Applications and Interpretation · Topic 3 · Geometry and trigonometry
3.15 Adjacency matrices
Construct an adjacency matrix from a graph, read its information, and use its powers to count walks between vertices.
1/5An adjacency matrix records a graph as a table of numbers
- An adjacency matrix records a graph as a table of numbers
- Constructing the matrix means filling the table cell by cell
- Rows and columns reveal degrees and edge counts
- Directed graphs give matrices that are not symmetric
- Powers of the matrix count walks between vertices
- Check your recall
- Practice: 10 questions
Part 1 of 5: An adjacency matrix records a graph as a table of numbers
A graph is easy to draw but awkward to process when it is large. A table of numbers is easier to store and calculate with. Recall that a graph has vertices joined by edges.
An adjacency matrix lists the vertices along both the rows and the columns. The entry in row and column counts the edges joining vertex to vertex .
Two vertices joined directly by an edge are adjacent. For a simple graph, the entries are only 0 or 1. A 1 means the vertices are adjacent, and a 0 means they are not.
Key terms · tap one for its definition
adjacency matrix
An adjacency matrix is a square matrix whose entry in row and column is the number of edges from vertex to vertex .
adjacent
Two vertices are adjacent if an edge joins them directly.
Part 2 of 5: Constructing the matrix means filling the table cell by cell
Start with a drawn graph and follow the same steps each time. Work one row at a time, because each row describes the edges at one vertex.
- Label the rows and columns with the vertices in the same order.
- Choose a row vertex and a column vertex.
- Write the number of edges joining them.
- Repeat until every cell is filled.
Each row of the finished matrix describes one vertex. Reading along it shows which vertices that vertex is joined to.
Worked example
Building an adjacency matrix
- Row P: P is joined to Q and R, giving 0,1,1,0.
- Row Q: Q is joined to P and R, giving 1,0,1,0.
- Row R: R is joined to P, Q and S, giving 1,1,0,1.
- Row S: S is joined to R only, giving 0,0,1,0.
Answer: .

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 3 of 5: Rows and columns reveal degrees and edge counts
Once the matrix is built, you can read facts from it directly. Add the entries in a row to find the degree of that vertex. In the matrix above, row R adds to 3.
Look at the main diagonal, which runs from top left to bottom right. For a simple graph, every entry there is 0. An undirected graph also gives a symmetric matrix, because each edge works in both directions.
The sum of all the entries is twice the number of edges. Each edge is counted once from each end.
Worked example
Reading a matrix
- The row sums are the degrees. Add them: .
- The total is twice the number of edges, so edges .
- The degree of the second vertex is its row sum, which is 3.
Answer: The graph has 6 edges, and the second vertex has degree 3.
Key terms · tap one for its definition
main diagonal
The main diagonal of a square matrix is the list of entries running from the top left to the bottom right.
symmetric matrix
A symmetric matrix is a square matrix in which the entry in row and column equals the entry in row and column .
Part 4 of 5: Directed graphs give matrices that are not symmetric
Now suppose each edge has an arrow, like a one-way street. A directed graph has edges with direction, so it matters which way each edge points.
The entry in row and column counts edges from vertex to vertex . Read across a row to see where edges leave. Read down a column to see where they arrive.
Worked example
A directed matrix
- Row P: edges leave P for Q and R, giving 0,1,1.
- Row Q: one edge leaves Q for R, giving 0,0,1.
- Row R: one edge leaves R for P, giving 1,0,0.
Answer: .
Key term
directed graph
A directed graph is a graph in which each edge has a direction, shown by an arrow from one vertex to another.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 5 of 5: Powers of the matrix count walks between vertices
Suppose you want routes that use exactly two edges. A walk is a sequence of edges in which each edge begins where the previous one ended. Vertices and edges may repeat.
The length of a walk is its number of edges. The entry in row and column of is the number of walks of length from vertex to vertex .
Worked example
Counting walks of length 2
- The entry for P to S is row P of times column S: .
- The entry for R to R is row R times column R: .
- Check the first walk: P to R to S has length 2.
Answer: There is 1 walk from P to S, and 3 walks from R to R.
A positive entry in means the two vertices are joined by a walk of length . A zero means there is none. For a simple graph, the diagonal of lists the degrees.
Key term
walk
A walk is a sequence of edges in which each edge begins at the vertex where the previous edge ended.
Check your recall[14 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.Write down[2 marks]
Write down the adjacency matrix for a graph with vertices A, B and C and edges AB and BC, using the order A, B, C.
Show mark schemeHide mark scheme
Model answer
.
- 1 mark for a matrix with zeros on the main diagonal
- 1 mark for entries of 1 in the positions for AB and BC, in both directions
- 2.State[2 marks]
State two features of the adjacency matrix of a simple undirected graph.
Show mark schemeHide mark scheme
Model answer
The main diagonal contains only zeros. The matrix is symmetric.
- 1 mark for stating that the main diagonal entries are zero
- 1 mark for stating that the matrix is symmetric
- 3.Determine[3 marks]
The adjacency matrix of a simple graph has row sums 3, 2, 2 and 1. Determine the number of edges and the degree of the first vertex.
Show mark schemeHide mark scheme
Model answer
The sum of the row sums is , which is twice the number of edges, so there are 4 edges. The first vertex has degree 3.
- 1 mark for adding the row sums to obtain 8
- 1 mark for halving to obtain 4 edges
- 1 mark for stating that the degree of the first vertex is 3
- 4.Explain[2 marks]
Explain why the adjacency matrix of a directed graph may not be symmetric.
Show mark schemeHide mark scheme
Model answer
Each entry counts edges from the row vertex to the column vertex. An edge from one vertex to another need not have a return edge, so the two entries can differ.
- 1 mark for stating that entries count edges from the row vertex to the column vertex
- 1 mark for explaining that an edge in one direction need not have a return edge
- 5.Calculate[3 marks]
A graph has adjacency matrix . Calculate the number of walks of length 2 from vertex 1 to vertex 2.
Show mark schemeHide mark scheme
Model answer
The entry is row 1 times column 2 of : . There is 1 walk of length 2.
- 1 mark for using row 1 and column 2 of
- 1 mark for multiplying and adding
- 1 mark for obtaining 1 walk
- 6.Deduce[2 marks]
The matrix of a simple graph has diagonal entries 3, 2, 2 and 1. Deduce the degree of each vertex, giving a reason.
Show mark schemeHide mark scheme
Model answer
Each diagonal entry of counts walks of length 2 from a vertex back to itself, which equals its degree. The degrees are 3, 2, 2 and 1.
- 1 mark for stating that the diagonal entries equal the degrees
- 1 mark for giving the degrees 3, 2, 2 and 1

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
EasyState[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: B · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation
MediumIdentify[2 marks]
Show answer and explanation
Answer: B · Worked explanation
MediumCalculate[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardDeduce[2 marks]
Show answer and explanation
Answer: D · Worked explanation
HardCalculate[2 marks]
Show answer and explanation
Answer: C · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation