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

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 the way an IB examiner expects — then try the practice questions and check your working against the mark scheme.

Practise Graph Theory questions → AI HL formula booklet

What's examined in AI HL graph theory

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

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

Solution

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

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: $AB=4$, $AC=5$, $BC=6$, $BD=3$, $CD=4$, $CE=7$, $DE=2$. Using Kruskal's algorithm, find the total weight of the minimum spanning tree.

Solution

1. List all edges in ascending order of their weights: $DE (2)$, $BD (3)$, $AB (4)$, $CD (4)$, $AC (5)$, $BC (6)$, $CE (7)$.

2. Select the smallest edge, $DE$, with weight $2$.

3. Add the next smallest edges, $BD (3)$ and $AB (4)$, as they do not form cycles.

4. Reject the edge $CD (4)$ because connecting $C$, $D$, and $B$ would form a closed cycle.

5. Add edge $AC (5)$ to connect vertex $C$ to the tree without forming a cycle. All $5$ vertices ($A, B, C, D, E$) are now connected.

6. Sum the selected edge weights: $2 + 3 + 4 + 5$. The total weight of the minimum spanning tree is $14$.

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\text{ km}$. The two shortest edges connected to vertex $A$ are $8\text{ km}$ and $11\text{ km}$. Calculate the lower bound for the Travelling Salesman Problem.

Solution

1. Identify the correct formula for the lower bound of the Travelling Salesman Problem (TSP): Weight of Residual MST $+$ sum of the two shortest edges incident to the removed vertex.

2. Extract the given weight of the residual minimum spanning tree: $28\text{ km}$.

3. Identify the lengths of the two shortest incident edges to vertex $A$: $8\text{ km}$ and $11\text{ km}$.

4. Sum these three values to calculate the lower bound: $28 + 8 + 11$.

5. The lower bound for the optimal tour is $47\text{ km}$.

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.

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{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}\).
Sketch the graph \(G\) clearly showing all vertices and edges.

Attempt it and see the mark scheme →

Question 2 · medium · 5 marks · Paper 1

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\).

Attempt it and see the mark scheme →

Question 3 · hard · 7 marks · Paper 1

A simplified internet network has 3 webpages. - Page 1 links to Page 2. - Page 2 links evenly to Page 1 and Page 3. - Page 3 links to Page 1.
(a) Write down the Google PageRank transition matrix \(T\) for this network. [2 marks]
(b) By solving the matrix equation \(T v = v\), algebraically find the exact steady-state PageRank vector \(v\). [5 marks]

Attempt it and see the mark scheme →

All 33 graph theory questions with mark schemes →

FAQ

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

There are 33 exam-style graph theory questions in the AI HL question bank (Paper 1: 24 · Paper 2: 9), graded 8 easy, 12 medium, 9 hard, 4 starter. 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: 24 · Paper 2: 9. 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.

More AI HL Unit 3 topics

← All IB Maths AI HL topics