3.14 Graph theory questions for IB Maths AI

48 questions on Graph theory, 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	22
Paper 2	25
Paper 3	1
Every paper	48

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-00311Paper 1 · 8 marks

The town of Ravensholm has six cycle-hire stations, P, Q, R, S, T and U. The cycle paths that join the stations directly are shown in the following graph.

Graph with six vertices P, Q, R, S, T, U and nine edges: PQ, PR, QR, QS, QT, RT, ST, SU, TU.

(a)
Write down the degree of each vertex.
2 marks
(b)
Use your answer to part (a) to find the number of cycle paths in the network.
2 marks
(c)
State, giving a reason, whether the graph is complete.
2 marks
(d)
The council wants to close some paths so that the remaining network is a tree that still contains all six stations. Find the number of paths that must be closed.
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-00312Paper 1 · 7 marks

Each of the seven members of a chess club, Amara, Bilal, Chen, Dafne, Emil, Freya and Goran, was asked how many other members of the club they had played this season. Any two members play each other at most once. Their replies, in order, were

5, 3, 4, 2, 6, 3, 2.

The situation is to be modelled by a simple graph in which the members are vertices and an edge joins two members who have played each other.

(a)
Explain why at least one of the replies must be incorrect.
2 marks
(b)
Dafne realises she has played three members, not two. All the other replies are correct.
Find the number of games that have been played between members of the club this season.
2 marks
(c)
The club wants every member to have played every other member exactly once by the end of the season. Find the number of games that still need to be played.
3 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-00313Paper 1 · 7 marks

The centre of the old town of Valdoria has five junctions, A, B, C, D and E. Every street between two junctions is one-way. The directed graph shows the streets and the direction in which traffic may travel along each one.

Directed graph with vertices A, B, C, D, E and seven directed edges: A to B, B to C, C to A, C to D, D to E, E to C, B to E.

(a)
Copy and complete the following table.
Junction
A
B
C
D
E
In-degree
Out-degree
3 marks
(b)
State, giving a reason, whether the graph is strongly connected.
2 marks
(c)
Road works mean that the direction of street CD is reversed, so that traffic travels from D to C. Determine whether it is still possible to drive from any junction to any other junction.
2 marks

The markschemeCheck this one with a free account

Practice all 48 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.14 Graph theory

Check your answers in Augment

A free account opens all 48 questions on Graph theory 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	–

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

Junction	A	B	C	D	E
In-degree
Out-degree

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

	$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 48 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	–

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