Practice AHL 3.14—Graph theory with authentic IB Mathematics Applications & Interpretation (AI) exam questions for both SL and HL students. This question bank mirrors Paper 1, 2, 3 structure, covering key topics like core principles, advanced applications, and practical problem-solving. Get instant solutions, detailed explanations, and build exam confidence with questions in the style of IB examiners.
Paper
Level
Question 1
HLPaper 2
A graph has the degree sequence:
1.[4]
Is this a valid simple graph? Justify using the Havel-Hakimi algorithm.
2.[1]
How many edges does the graph contain?
Question 2
HLPaper 2
What is the minimum number of edges in a connected graph with 6 vertices?
1.[2]
What is the minimum number of edges in a connected graph with 6 vertices?
Question 3
HLPaper 2
A graph G has an adjacency matrix A . You are told that the entry .
1.[2]
What does this entry represent?
2.[3]
How can this information be used in analyzing graph connectivity?
Question 4
HLPaper 1
The position vector of a particle, P, relative to a fixed origin O at time t is given by
1.[2]
Find the velocity vector of P.
2.[5]
Show that the acceleration vector of P is never parallel to the position vector of P.
Question 5
HLPaper 2
Based on the graph:
1.[3]
Using Kruskal's algorithm, determine the minimum spanning tree, and state its weight.
2.[3]
Using Prim's algorithm starting at vertex D, determine the minimum spanning tree, and state its weight.
Question 6
HLPaper 2
Based on the graph:
1.[3]
Create the complete weighted adjacency matrix (including the shortest weighted connection between every two vertices).
2.[3]
Find the upper bound for the travelling salesman problem using vertex A.
Question 7
HLPaper 2
Based on this graph:
1.[2]
Create the adjacency matrix.
2.[1]
Find a hamiltonian path in this graph
3.[1]
What change would be needed for a hamiltonian cycle to be present?
Question 8
HLPaper 2
Based on the graph:
1.[4]
Solve the Chinese Postman's problem for this graph.
Question 9
HLPaper 2
Based on the graph:
1.[2]
Create an unweighted adjacency matrix for the graph.
2.[1]
Hence, identify the odd vertices.
3.[4]
Hence, find the solution to the chinese postman problem.
Question 10
HLPaper 1
The diagram below shows a network of roads in a small village with the weights indicating the distance of each road, in metres, and junctions indicated with letters. 
Musab is required to deliver leaflets to every house on each road. He wishes to minimize his total distance.
1.[5]
Musab starts and finishes from the village bus-stop at A. Determine the total distance Musab will need to walk.
2.[2]
Instead of having to catch the bus to the village, Musab's sister offers to drop him off at any junction and pick him up at any other junction of his choice. Explain which junctions Musab should choose as his starting and finishing points.