3.15 Adjacency matrices questions for IB Maths AI

36 questions on Adjacency matrices, written by Augment in the style of IB exam papers. Six of them are below in full, to answer on paper.

IB Mathematics: Applications and Interpretation
Part of 3 Geometry and trigonometry
HL only

Questions by paper and level

Paper	Questions
Paper 1	14
Paper 2	21
Paper 3	1
Every paper	36

Counted on 10 November 2026

Questions to try

Written by Augment in the style of IB exams, not past papers. Answer them on paper, then check each one against its markscheme with a free account.

Question 1 · AI-00481Paper 1 · 6 marks

A farm has six water storage tanks, $P$ , $Q$ , $R$ , $S$ , $T$ and $U$ . Pipes can be laid directly between any two tanks. The following table shows the length, in metres, of pipe needed between each pair of tanks.

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

The farmer, Amaru, wants to connect all six tanks using the minimum total length of pipe.

(a)
Use Prim's algorithm, starting at $P$ , to find the minimum spanning tree. Show clearly the order in which the edges are selected.
4 marks
(b)
Find the minimum total length of pipe needed.
2 marks

The markschemeCheck this one with a free account

Question 2 · AI-00439Paper 2 · 14 marks

A ferry company serves five islands: Arlo (A), Brae (B), Cove (C), Dunn (D) and Eske (E). Ferries run in both directions on each of the following direct routes, and there are no other direct routes.

A–B, A–C, B–C, B–D, B–E, C–E, D–E

The adjacency matrix $M$ of this network has rows and columns in the order A, B, C, D, E.

(a)
Write down $M$ .
2 marks
(b)
Explain why $M$ is equal to its transpose (it is symmetric about its leading diagonal).
1 mark
(c)
Find $M^{2}$ .
2 marks
(d)
Interpret the element in row 2, column 2 of $M^{2}$ in context.
1 mark
(e)
Find the number of ways of travelling from Arlo to Eske using exactly three ferry journeys.
2 marks
(f)
Find the total number of ways of making exactly four ferry journeys that start and finish at the same island.
2 marks
(g)
Find the number of ways of travelling from Arlo to Dunn using at most three ferry journeys.
3 marks
(h)
Explain why your answer to part (g) may be more than the number of sensible routes a passenger would take.
1 mark

The markschemeCheck this one with a free account

Question 3 · AI-01629Paper 3 · 28 marks

The purpose of this question is to use graph theory to plan two kinds of inspection route around an irrigation network.

Valentina is the engineer for a vineyard cooperative near Mendoza, Argentina. Water is pumped between seven pumping stations, $P$ , $Q$ , $R$ , $S$ , $T$ , $U$ and $V$ , along underground pipelines. A service track runs beside every pipeline. The graph shows the stations and the lengths of the service tracks, in km. Valentina's office is at station $P$ .

Weighted graph of seven pumping stations P, Q, R, S, T, U, V. Edges in km: PQ 5, PR 6, PU 9, QR 4, QS 8, QV 7, RS 7, ST 3, SU 5, TU 6, TV 4. — Diagram not to scale.

The total length of the service tracks is 64 km.

Once a year Valentina drives along every service track to check the pipelines for leaks.

(a)
Explain why Valentina cannot start and finish at $P$ and drive along every service track exactly once.
2 marks
(b)
Find the length of the shortest route that starts and finishes at $P$ and travels along every service track at least once.
5 marks
(c)
In some years a colleague collects Valentina at the end of her inspection, so her route must start at $P$ but can finish at any station.
Determine where her route should finish to make it as short as possible, and find the length of this route.
3 marks
(d)
Write down the adjacency matrix $M$ for the graph, with the vertices in the order $P, Q, R, S, T, U, V$ .
2 marks
(e)
Find the number of walks of length 4 from $P$ to $T$ .
2 marks
(f)
Valentina also has to visit every pumping station to read its meters, starting and finishing at $P$ . She does not need to travel along every track. She draws up the following table of least distances, in km, between the stations.
$P$
$Q$
$R$
$S$
$T$
$U$
$Q$
5
$R$
6
4
$S$
13
8
7
$T$
$a$
11
10
3
$U$
9
13
12
5
6
$V$
12
7
$b$
7
4
$c$
Find the values of $a$ , $b$ and $c$ .
3 marks
(g)
Use the nearest neighbour algorithm, starting at $P$ , to find an upper bound for the length of Valentina's meter-reading route.
3 marks
(h)
By first deleting vertex $P$ , use the deleted vertex algorithm to find a lower bound for the length of this route.
4 marks
(i)
Valentina finds that deleting vertex $T$ instead gives a lower bound of 35 km.
Find a cycle that visits every station and has a length less than your answer to part (g). Hence state the narrowest interval, from this question, that must contain the length $L$ km of the shortest meter-reading route.
3 marks
(j)
Explain why, if Valentina drives the route found in part (g), she will pass through one of the stations twice.
1 mark

	$P$	$Q$	$R$	$S$	$T$	$U$
$Q$	5
$R$	6	4
$S$	13	8	7
$T$	$a$	11	10	3
$U$	9	13	12	5	6
$V$	12	7	$b$	7	4	$c$

The markschemeCheck this one with a free account

Question 4 · AI-00945Paper 1 · 6 marks

A sculpture is made from eight metal rods welded together to form the frame of a square-based pyramid. The frame is represented by the graph below, where the vertices are the corners A, B, C, D and E and the edges are the rods.

Graph of a square-based pyramid frame: base vertices A, B, C, D joined in the cycle A–B–C–D–A, and apex E joined to each of A, B, C and D. Eight edges.

(a)
Write down the adjacency matrix $M$ for the graph, with the vertices in the order A, B, C, D, E.
2 marks
(b)
An ant walks along the rods. Find the number of different walks of length 4 that start at A and end at C.
2 marks
(c)
Find the number of different walks of length 3 that start and end at E.
2 marks

The markschemeCheck this one with a free account

Question 5 · AI-00493Paper 2 · 17 marks

A museum has six galleries, $A$ , $B$ , $C$ , $D$ , $E$ and $F$ . The following graph shows which galleries are joined by a doorway. The weight of each edge is the walking time, in minutes, between the centres of the two galleries.

Weighted graph of doorways between galleries A to F. Walking times in minutes: AB 4, AC 6, BC 3, BD 5, CD 4, BE 9, DE 3, DF 5, CF 10, EF 4. — Diagram not to scale.

(a)
Write down the adjacency matrix $M$ for the doorways, with rows and columns in the order $A$ to $F$ .
2 marks
(b)
Find the number of different ways of walking from gallery $B$ to gallery $C$ by passing through exactly three doorways.
2 marks
(c)
A security guard, Ines, wants to walk through every doorway exactly once. Explain why this is possible, and state the galleries in which she must start and finish.
3 marks
(d)
The following table shows the least walking times, in minutes, between the galleries. Find the values of $p$ , $q$ , $r$ and $s$ .
$A$
$B$
$C$
$D$
$E$
$F$
$A$
–
4
6
$p$
$q$
$r$
$B$
4
–
3
5
8
10
$C$
6
3
–
4
7
$s$
$D$
$p$
5
4
–
3
5
$E$
$q$
8
7
3
–
4
$F$
$r$
10
$s$
5
4
–
2 marks
(e)
A tour guide starts at the entrance gallery $A$ , visits every gallery and returns to $A$ . Use the nearest neighbour algorithm on the table to find an upper bound for the walking time of the tour.
3 marks
(f)
By deleting vertex $D$ and using Prim's algorithm starting at $A$ , find a lower bound for the walking time of the tour.
4 marks
(g)
Let $W$ be the least walking time of the tour. Write down an inequality for $W$ .
1 mark

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	4	6	$p$	$q$	$r$
$B$	4	–	3	5	8	10
$C$	6	3	–	4	7	$s$
$D$	$p$	5	4	–	3	5
$E$	$q$	8	7	3	–	4
$F$	$r$	10	$s$	5	4	–

The markschemeCheck this one with a free account

Question 6 · AI-00946Paper 1 · 7 marks

In a nature park, visitors must follow one-way trails between five viewpoints, P, Q, R, S and T. The directed graph shows the trails.

Directed graph with vertices P, Q, R, S, T and arrows P to Q, Q to R, R to P, Q to S, S to T, T to Q, R to T and T to P.

(a)
Write down the adjacency matrix $A$ for the graph, with the viewpoints in the order P, Q, R, S, T.
2 marks
(b)
Find the number of different ways to walk from P to S using exactly five trails.
2 marks
(c)
Write down one of these ways, as a sequence of viewpoints.
1 mark
(d)
State, giving a reason, whether the graph is strongly connected.
2 marks

The markschemeCheck this one with a free account

Practice all 36 in Augment

Free with an account. Every question has its markscheme, and Augment keeps the ones you got wrong so you can come back to them.

Start free Log in

The notes on 3.15 Adjacency matrices

Check your answers in Augment

A free account opens all 36 questions on Adjacency matrices with their markschemes, and keeps a record of what you have marked.

Start free

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	4	6	$p$	$q$	$r$
$B$	4	–	3	5	8	10
$C$	6	3	–	4	7	$s$
$D$	$p$	5	4	–	3	5
$E$	$q$	8	7	3	–	4
$F$	$r$	10	$s$	5	4	–

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	4	6	$p$	$q$	$r$
$B$	4	–	3	5	8	10
$C$	6	3	–	4	7	$s$
$D$	$p$	5	4	–	3	5
$E$	$q$	8	7	3	–	4
$F$	$r$	10	$s$	5	4	–

Questions by paper and level

Questions to try

Practice all 36 in Augment

More questions in Geometry and trigonometry

Check your answers in Augment

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	4	6	$p$	$q$	$r$
$B$	4	–	3	5	8	10
$C$	6	3	–	4	7	$s$
$D$	$p$	5	4	–	3	5
$E$	$q$	8	7	3	–	4
$F$	$r$	10	$s$	5	4	–