An undirected graph has $4$ vertices labelled $A$, $B$, $C$, and $D$. Its adjacency matrix $M$ is given by $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$. Calculate the exact number of walks of length $3$ between vertex $A$ and vertex $C$.

1. Identify that the number of walks of length $k$ between vertices in a graph is found by raising its adjacency matrix to the power $k$. 2. Enter the $4 \times 4$ adjacency matrix $M$ into your Graphic Display Calculator. 3. Calculate the matrix power $M^3$ using the GDC matrix workspace. 4. Extract the value located in the 1st row (for vertex $A$) and 3rd column (for vertex $C$) of the resulting matrix. 5. The matrix $M^3$ evaluates to $\begin{pmatrix} 2 & 5 & 5 & 2 \\ 5 & 4 & 5 & 5 \\ 5 & 5 & 4 & 5 \\ 2 & 5 & 5 & 2 \end{pmatrix}$. The exact number of walks is $5$ .

An unweighted adjacency matrix for graph $G$ is $A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ . Calculate $A^3$ . State the geometric meaning of the number in Row 1, Column 3 of the matrix $A^3$ .

Square the matrix: $A^2 = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ M1A1 Multiply by $A$ again: $A^3 = A^2 A = \begin{pmatrix} 0 & 2 & 0 \\ 2 & 0 & 2 \\ 0 & 2 & 0 \end{pmatrix}$ A1 The entry in Row 1, Column 3 is $0$ . A1 Meaning: there are no walks of length 3 from Vertex 1 to Vertex 3. R1

Home › IB Maths AI HL › Questions by topic › Graph Theory

IB Maths AI HL · Unit 3: Geometry and Trigonometry

IB Maths AI HL Graph Theory Questions

Updated October 2026

Exam-style IB Maths AI HL graph theory questions with worked solutions. Start with the 3 fully worked examples below — each is solved step by step, showing the working that earns the marks — then try the practice questions and check your working against the mark scheme.

86 questions
Paper 1: 56
Paper 2: 30
23 easy
34 medium
25 hard
4 very hard
3 worked examples

Practise Graph Theory questions →

What you need to know

Vertices, edges and the adjacency matrix, where the (i, j) entry of Aⁿ counts the walks of length n. Then minimum spanning trees with Kruskal and Prim, Eulerian and Hamiltonian circuits, and the Chinese postman problem, each with a worked example. Graph theory — adjacency matrices, spanning trees and route problems overview →

What's examined in AI HL graph theory

The question bank covers these graph theory question types (number of questions in brackets):

Graph Algorithms (60)
Graph Properties & Walks (15)
Adjacency Matrices (11)

Where students lose marks on graph theory

Examiner's noteGraph algorithms: Prim vs nearest neighbour, no method shown, bounds mixed up

Where marks are lost: Prim's algorithm and the nearest-neighbour algorithm were confused; Prim's was done "by eye" with no order of edges (the vertex order does not show the algorithm); the stopping rule was not stated; the cycle did not return to the start or repeated vertices; a spanning tree was treated as a path; the best upper bound was not the smallest, and the deleted-vertex lower bound was not understood. The reports call method "all important" in algorithms.

Examiners flagged this in 4 exam series (May 2024, November 2024, May 2025, November 2025). Summarised in our own words from IB subject reports, IB Programme Resource Centre. Read the full note →

Graph Theory worked examples

Worked example 1: Finding Walks using Adjacency Matrices · easy

An undirected graph has $4$ vertices labelled $A$ , $B$ , $C$ , and $D$ . Its adjacency matrix $M$ is given by $M = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix})$ . Calculate the exact number of walks of length $3$ between vertex $A$ and vertex $C$ .

Solution

5 steps

Examiner tip: Remember that the main diagonal of

M^{1}

shows loops, and

M^{2}

shows paths of length 2 which include returning to the same vertex. Always ensure you are reading the correct row-column intersection for the required vertices.

Worked example 2: Finding a Minimum Spanning Tree · medium

A connected, weighted graph has edges with the following weights: $A B = 4$ , $A C = 5$ , $B C = 6$ , $B D = 3$ , $C D = 4$ , $C E = 7$ , $D E = 2$ . Using Kruskal's algorithm, find the total weight of the minimum spanning tree.

Solution

6 steps

Examiner tip: Always physically cross out edges that form a cycle on your working paper so you do not accidentally include them in your final minimum spanning tree sum.

Worked example 3: Calculating the TSP Lower Bound · hard

A delivery driver must visit $5$ towns ( $A$ , $B$ , $C$ , $D$ , $E$ ) and return to the start. The graph of the distances is fully connected. Removing vertex $A$ and all its incident edges leaves a residual graph whose minimum spanning tree has a weight of $28 km$ . The two shortest edges connected to vertex $A$ are $8 km$ and $11 km$ . Calculate the lower bound for the Travelling Salesman Problem.

Solution

5 steps

Examiner tip: The lower bound for the Travelling Salesman Problem is often not a valid closed tour itself, but it guarantees that no valid Hamiltonian cycle can possibly have a shorter distance.

Try these IB Maths AI HL graph theory questions

Three questions from the bank, easiest first. Mark schemes and AI marking of your written working are in the practice area. One of them has its full worked solution here, open to everyone.

Question 1 · easy · 4 marks · Paper 1

An undirected graph $G$ has 4 vertices: A, B, C, and D.
Its adjacency matrix is given by: $M = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix})$ .
Sketch the graph $G$ clearly showing all vertices and edges.

Determine the degree of every vertex in $G$ . Hence, state whether the graph contains an Eulerian trail, and justify your answer.

Attempt it and see the mark scheme →

Question 2 · medium · 5 marks · Paper 1

An unweighted adjacency matrix for graph $G$ is $A = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})$ .
Calculate $A^{3}$ . State the geometric meaning of the number in Row 1, Column 3 of the matrix $A^{3}$ .

Full worked solution Free, no sign-in

Square the matrix: $A^{2} = (\begin{matrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{matrix})$ M1A1
Multiply by $A$ again: $A^{3} = A^{2} A = (\begin{matrix} 0 & 2 & 0 \\ 2 & 0 & 2 \\ 0 & 2 & 0 \end{matrix})$ A1
The entry in Row 1, Column 3 is $0$ . A1
Meaning: there are no walks of length 3 from Vertex 1 to Vertex 3. R1

Every question here has a full worked solution. See them all →

Question 3 · hard · 8 marks · Paper 1

The town of Königsberg has a snow-plowing network defined by a weighted graph with the following odd-degree vertices: $V_{1}, V_{2}$ . The shortest path between $V_{1}$ and $V_{2}$ has a weight of $12$ . The total weight of all edges in the network is $150$ .
A snowplow must traverse every edge in the graph at least once and return to its starting position (The Chinese Postman Problem).
Calculate the minimum total distance the snowplow must travel. Explain your reasoning regarding Eulerian circuits.

Attempt it and see the mark scheme →

Free account — sign in to download Topic PDF: 7 questions with worked answers · 4 pages · 143 KB

All 86 graph theory questions with mark schemes →

Save your progress and get 5 more questions on every topic, checked instantly. Free account, no card. Join free

Revise graph theory for the exam

FAQ

How many IB Maths AI HL graph theory questions are there?

There are 86 exam-style graph theory questions in the AI HL question bank (Paper 1: 56 · Paper 2: 30), graded 23 easy, 34 medium, 25 hard, 4 very hard. Every question has a full IB-style mark scheme (M, A and R marks).

Is graph theory on Paper 1 or Paper 2?

Both. In the bank, Paper 1: 56 · Paper 2: 30. Practise with your GDC — AI papers expect calculator methods throughout.

Where can I get the mark schemes?

Open the AI HL Unit 3 practice page: every question has a step-by-step IB-style mark scheme, and you can photograph your working for instant AI marking. The worked examples on this page are free.

What else is free here

Save your answers and track your progressA free account remembers the questions you have done on every topic and brings you back to this page.

Join free

Already have an account? Sign in

Teaching this topic?

Free ready-to-teach lessons (slides and teacher notes): Graph theory — adjacency & weighted matrices · Minimum spanning trees (Kruskal's & Prim's algorithms) · Travelling salesman problem: upper & lower bounds.

IB Maths AI HL Graph Theory Questions

Try it first

What you need to know

What's examined in AI HL graph theory

Where students lose marks on graph theory

Graph Theory worked examples

Worked example 1: Finding Walks using Adjacency Matrices · easy

Solution

Worked example 2: Finding a Minimum Spanning Tree · medium

Solution

Worked example 3: Calculating the TSP Lower Bound · hard

Solution

Try these IB Maths AI HL graph theory questions

Question 1 · easy · 4 marks · Paper 1

Question 2 · medium · 5 marks · Paper 1

Full worked solution Free, no sign-in

Question 3 · hard · 8 marks · Paper 1

Revise graph theory for the exam

FAQ

What else is free here

Teaching this topic?

More AI HL Unit 3 topics