Graph theory: IB Mathematics: Applications & Interpretation questions with answers
Free Graph theory questions for IB Mathematics: Applications & Interpretation (SL & HL), HL only, part of Geometry & trigonometry. Each question has the answer and the marking points an examiner would look for.
A road inspector must travel along every road shown in the table at least once, starting and finishing at A. The table gives the lengths of the roads in km.
Road
AB
BC
CD
DA
AC
Length
6
8
4
8
9
Table 1.1
(a)
Identify the vertices of odd degree.
[2]
(b)
Find the length of the shortest route for the inspector.
[4]
Show answers and mark scheme
Part
Answer and marking points
Marks
(a)
A and C
degrees A 3, B 2, C 3, D 2 (M1) A and C A1
2
(b)
44 km
total length of roads = 35 A1 repeat the shortest path between the odd vertices M1 shortest A to C = 9 A1 44 km A1
4
Question 2Structured · 5 marks
The adjacency matrix of a graph G with vertices A, B, C and D is shown.
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
0
1
D
0
1
1
0
Table 2.1
(a)
Write down the degree of vertex B, and state whether G has an Eulerian circuit, giving a reason.
[3]
(b)
Find the number of walks of length 3 from A to C.
[2]
Show answers and mark scheme
Part
Answer and marking points
Marks
(a)
deg B = 3
deg B = 3 A1 degrees 2, 3, 3, 2 (M1) no, not all degrees are even R1
3
(b)
5
(M3)AC(M1) 5 A1
2
Question 3Structured · 6 marks
The table shows the cost, in thousands of dollars, of laying cable between 5 villages. Blank cells mean a cable cannot be laid directly.
A
B
C
D
E
A
–
82
73
B
82
–
89
54
54
C
89
–
52
D
73
54
52
–
46
E
54
46
–
Table 3.1
Use Kruskal’s algorithm to find a minimum spanning tree, stating the order in which edges are added, and find its total cost.
[6]
Show answers and mark scheme
Part
Answer and marking points
Marks
225
edges chosen in increasing order of weight M1 avoiding cycles M1 edges: DE (46), CD (52), BD (54), AD (73) A2 minimum spanning tree drawn or listed A1 total 225 A1
6
Question 4Structured · 6 marksA* challenge
The weights of edges in a complete graph are shown.
A
B
C
D
E
A
–
16
4
18
12
B
16
–
13
4
8
C
4
13
–
17
15
D
18
4
17
–
4
E
12
8
15
4
–
Table 4.1
Use Prim’s algorithm, starting at A, to find a minimum spanning tree, listing the edges in the order they are added, and state its weight.
[6]
Show answers and mark scheme
Part
Answer and marking points
Marks
24
Prim’s algorithm applied M1 order: AC (4), AE (12), ED (4), DB (4) A3 tree drawn or listed A1 weight 24 A1
6
Question 5Structured · 14 marksA* challenge
A courier must visit five towns, starting and finishing at A. The table shows the travel times in minutes between the towns.
A
B
C
D
E
A
–
10
40
42
40
B
10
–
30
36
41
C
40
30
–
32
57
D
42
36
32
–
32
E
40
41
57
32
–
Table 5.1
(a)
Explain why the table represents a complete graph.
[1]
(b)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the travelling salesman problem.
[4]
(c)
By deleting vertex A, use the deleted vertex algorithm to find a lower bound.
[5]
(d)
Write down an interval for the length T of the optimal route.
[1]
(e)
Find the number of different Hamiltonian cycles starting and finishing at A, and explain why checking all of them is not practical for larger networks.
Riyaz Shaikh has mentored IGCSE, IB and A Level students for 15+ years, one-on-one, online and in Mumbai. The hardest questions on this site are the ones he uses to find a student's weak points.
Original IB-style practice questions written for mentorriyaz.in. These are not IB past paper questions, and this site is not affiliated with or endorsed by the International Baccalaureate Organization. Updated 2026-11-04. Paper generator · mentorriyaz.in