3.16 Tree and cycle algorithms questions for IB Maths AI

36 questions on Tree and cycle algorithms, 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	17
Paper 2	18
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-00480Paper 1 · 6 marks

A university is laying fibre-optic cable to connect seven buildings, $A$ , $B$ , $C$ , $D$ , $E$ , $F$ and $G$ . The cable can only be laid along the service tunnels shown in the following graph. The weight of each edge is the length of the tunnel, in metres.

Weighted graph with vertices A to G. Edges in metres: AB 45, AC 52, BC 38, BD 41, CD 36, BE 60, DE 33, DF 47, CF 55, EF 50, EG 29, FG 40. — Diagram not to scale.

The university wants every building to be connected to the network using the least total length of cable.

(a)
Use Kruskal's algorithm to find the minimum spanning tree of the graph. List the edges in the order in which they are added.
3 marks
(b)
Write down the total length of cable needed.
1 mark
(c)
The cable costs 12.40 Swiss francs (CHF) per metre. Calculate the cost of the cable.
2 marks

The markschemeCheck this one with a free account

Question 2 · AI-00490Paper 2 · 16 marks

A mobile library van serves seven villages in rural Wales, $A$ , $B$ , $C$ , $D$ , $E$ , $F$ and $G$ . The roads between the villages are shown in the following graph. The weights are the lengths of the roads, in km.

Weighted graph of roads between villages A to G. Lengths in km: AB 24, BC 31, CD 18, DE 27, EF 22, FA 20, GA 26, GB 19, GD 23, GE 16. — Diagram not to scale.

(a)
State, with a reason, whether the graph has an Eulerian trail.
2 marks
(b)
The following table shows the least distances, in km, between the villages. Find the values of $a$ , $b$ , $c$ and $d$ .
$A$
$B$
$C$
$D$
$E$
$F$
$G$
$A$
–
24
$a$
$b$
42
20
26
$B$
24
–
31
42
$c$
44
19
$C$
$a$
31
–
18
45
$d$
41
$D$
$b$
42
18
–
27
49
23
$E$
42
$c$
45
27
–
22
16
$F$
20
44
$d$
49
22
–
38
$G$
26
19
41
23
16
38
–
2 marks
(c)
The van is based at $G$ . Use the nearest neighbour algorithm, starting at $G$ , to find an upper bound for the length of a route that visits every village and returns to $G$ .
3 marks
(d)
By deleting vertex $G$ and using Kruskal's algorithm on the table, find the minimum spanning tree of the remaining six vertices. Sketch the tree and write down its weight.
4 marks
(e)
Hence find a lower bound for the length of the route.
2 marks
(f)
Deleting vertex $A$ instead gives a lower bound of 142 km. Explain why the lower bound in part (e) is more useful.
1 mark
(g)
Let $L$ be the length of the shortest route that visits every village and returns to $G$ . Write down the best inequality for $L$ found so far.
2 marks

	$A$	$B$	$C$	$D$	$E$	$F$	$G$
$A$	–	24	$a$	$b$	42	20	26
$B$	24	–	31	42	$c$	44	19
$C$	$a$	31	–	18	45	$d$	41
$D$	$b$	42	18	–	27	49	23
$E$	42	$c$	45	27	–	22	16
$F$	20	44	$d$	49	22	–	38
$G$	26	19	41	23	16	38	–

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-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 5 · AI-00491Paper 2 · 19 marks

Eleni sells handmade jewellery on five Greek islands, $A$ , $B$ , $C$ , $D$ and $E$ . She lives on island $A$ . The following table shows the cost, in euros (EUR), of a ferry ticket between islands. There is no direct ferry between $B$ and $D$ .

	$A$	$B$	$C$	$D$	$E$
$A$	–	38	45	29	47
$B$	38	–	33	–	41
$C$	45	33	–	42	36
$D$	29	–	42	–	49
$E$	47	41	36	49	–

(a)
The table is represented by a graph whose vertices are the islands and whose edges are the direct ferry routes. Explain why this graph is not complete.
1 mark
(b)
Use Kruskal's algorithm to find the minimum spanning tree of the graph. State the order in which the edges are added and the weight of the tree.
3 marks
(c)
Hence write down an upper bound for the cost of a trip that starts and finishes at $A$ and visits every island.
1 mark
(d)
Write down the least cost of travelling between $B$ and $D$ .
1 mark
(e)
Use the nearest neighbour algorithm, starting at $A$ , to find a better upper bound for the cost of the trip.
3 marks
(f)(i)
By deleting vertex $A$ , find a lower bound for the cost of the trip.
3 marks
(f)(ii)
By deleting vertex $C$ , find a second lower bound for the cost of the trip.
3 marks
(g)
Let $T$ be the cost of Eleni's cheapest trip. Using your answers, write down the best inequality for $T$ .
2 marks
(h)
Find a trip that starts and finishes at $A$ and costs less than the upper bound in part (e). State its cost.
2 marks

The markschemeCheck this one with a free account

Question 6 · AI-00482Paper 1 · 7 marks

After a snowstorm, a plough must clear every road in a small town in Norway. The roads and their lengths, in km, are shown in the following graph. The plough is kept at the depot at junction $P$ .

Weighted graph of roads between junctions P, Q, R, S, T, U. Lengths in km: PQ 1.4, QR 1.1, RS 0.9, ST 1.6, TU 1.0, UP 1.3, QU 0.8, RT 1.5, QT 2.0. — Diagram not to scale.

(a)
Write down the vertices of odd degree.
1 mark
(b)
The plough must travel along every road at least once, starting and finishing at $P$ . Find the minimum distance it must travel.
3 marks
(c)
Write down the roads that the plough travels along twice.
1 mark
(d)
The plough travels at an average speed of $18 {km h}^{- 1}$ . Find the time it takes to complete the route in part (b), in minutes.
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.16 Tree and cycle algorithms

Check your answers in Augment

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

Start free

	$A$	$B$	$C$	$D$	$E$	$F$	$G$
$A$	–	24	$a$	$b$	42	20	26
$B$	24	–	31	42	$c$	44	19
$C$	$a$	31	–	18	45	$d$	41
$D$	$b$	42	18	–	27	49	23
$E$	42	$c$	45	27	–	22	16
$F$	20	44	$d$	49	22	–	38
$G$	26	19	41	23	16	38	–

	$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$
$A$	–	38	45	29	47
$B$	38	–	33	–	41
$C$	45	33	–	42	36
$D$	29	–	42	–	49
$E$	47	41	36	49	–

	$A$	$B$	$C$	$D$	$E$	$F$	$G$
$A$	–	24	$a$	$b$	42	20	26
$B$	24	–	31	42	$c$	44	19
$C$	$a$	31	–	18	45	$d$	41
$D$	$b$	42	18	–	27	49	23
$E$	42	$c$	45	27	–	22	16
$F$	20	44	$d$	49	22	–	38
$G$	26	19	41	23	16	38	–

	$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$
$A$	–	38	45	29	47
$B$	38	–	33	–	41
$C$	45	33	–	42	36
$D$	29	–	42	–	49
$E$	47	41	36	49	–

Questions by paper and level

Questions to try

Practice all 36 in Augment

More questions in Geometry and trigonometry

Check your answers in Augment

	$A$	$B$	$C$	$D$	$E$	$F$	$G$
$A$	–	24	$a$	$b$	42	20	26
$B$	24	–	31	42	$c$	44	19
$C$	$a$	31	–	18	45	$d$	41
$D$	$b$	42	18	–	27	49	23
$E$	42	$c$	45	27	–	22	16
$F$	20	44	$d$	49	22	–	38
$G$	26	19	41	23	16	38	–

	$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$
$A$	–	38	45	29	47
$B$	38	–	33	–	41
$C$	45	33	–	42	36
$D$	29	–	42	–	49
$E$	47	41	36	49	–