Unit 3: Geometry and Trigonometry
Topic 3.14: Graph theory (HL only) Questions
Practice 20 exam-style questions for IB Math AI SL Topic 3.14. Review the question stems below, then unlock the full Question Bank to access markschemes, model answers, and AI grading.
11 mark
2026
A 'path' through a graph is a route that:
Markscheme and model answer locked
Unlock Question3Write down1 mark
2026
Six towns are joined by roads. The towns are the vertices A, B, C, D, E and H of a weighted graph, and the lengths of the roads, in kilometres, are shown in the table. A maintenance team has its base at H and must inspect every road.
Write down the degree of H.
| Road | Length |
|---|---|
| HA | 11 |
| HC | 14 |
| AB | 9 |
| AE | 16 |
| BC | 12 |
| BD | 15 |
| CD | 10 |
| CE | 13 |
| DE | 8 |
Write down the degree of H.
Markscheme and model answer locked
Unlock Question4State1 mark
2026
Six sorting points are joined by streets. The points are the vertices K, L, M, N, P and Q of a weighted graph, and the lengths of the streets, in hundreds of metres, are shown in the table. A maintenance team has its base at M and must inspect every road.
The team plan to travel along each road exactly once, starting and ending at M.
State a reason why this plan is not possible.
| Road | Length |
|---|---|
| KN | 17 |
| KL | 12 |
| KM | 9 |
| LN | 14 |
| LP | 18 |
| MN | 11 |
| MP | 16 |
| MQ | 7 |
| NP | 10 |
| NQ | 8 |
The team plan to travel along each road exactly once, starting and ending at M.
State a reason why this plan is not possible.
Markscheme and model answer locked
Unlock Question5Explain2 marks
2026
A weighted graph has vertices for five towns: Ashby (A), Bexley (B), Carden (C), Dalton (D), Eston (E). Each edge weight is the fare, in pounds, of the cheapest direct train between two towns. The edges are listed below.
Explain why the graph can be described as "connected", but not "complete".
| Edge | Weight |
|---|---|
| AC | 76 |
| AD | 57 |
| AE | 47 |
| BC | 38 |
| BD | 39 |
| BE | 37 |
| CD | 42 |
| CE | 70 |
| DE | 88 |
Explain why the graph can be described as "connected", but not "complete".
Markscheme and model answer locked
Unlock Question6State1 mark
2026
A delivery driver must visit six warehouses, A, B, C, D, E and F. The roads between some pairs of warehouses, with their lengths in kilometres, are listed.
State, with a reason, whether the graph contains an Eulerian circuit.
| Road | AB | AC | AD | BC | BE | CD | CF | DE | DF | EF |
|---|---|---|---|---|---|---|---|---|---|---|
| Length (km) | 14 | 22 | 30 | 10 | 25 | 12 | 27 | 9 | 16 | 11 |
State, with a reason, whether the graph contains an Eulerian circuit.
Markscheme and model answer locked
Unlock Question7Explain2 marks
2026
A weighted graph has vertices for five islands: Arne (A), Brava (B), Corro (C), Dunmore (D), Elsby (E). Each edge weight is the fare, in euros, of the cheapest direct ferry between two islands. The edges are listed below.
Explain why the graph can be described as "connected", but not "complete".
| Edge | Weight |
|---|---|
| AB | 92 |
| AC | 55 |
| AD | 32 |
| AE | 39 |
| BC | 93 |
| BD | 54 |
| BE | 94 |
| CD | 43 |
| DE | 33 |
Explain why the graph can be described as "connected", but not "complete".
Markscheme and model answer locked
Unlock Question8Find2 marks
2026
A water-supply network is connected, has 12 junctions and is a tree (no loops/cycles).
(a) Find the number of pipes (edges).
(b) Explain what removing one pipe does to the supply.
(a) Find the number of pipes (edges).
(b) Explain what removing one pipe does to the supply.
Markscheme and model answer locked
Unlock Question9Find3 marks
2026
A computer network connects 6 servers with these cables: 1–2, 1–3, 2–3, 3–4, 4–5, 4–6, 5–6. Find the degree of each server, and verify the handshake lemma.
Markscheme and model answer locked
Unlock Question10Determine2 marks
2026
Seven towns, A to G, are joined by roads. The table lists each road and its length in kilometres; there are no other roads.
Determine whether it is possible to make a journey that starts and finishes at different towns and uses every road exactly once. Give a reason for your answer.
| Road | AB | AC | AD | BD | BF | CD | CE | DE | DF | EF | EG | FG |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Length (km) | 11 | 6 | 11 | 9 | 10 | 8 | 9 | 8 | 3 | 11 | 17 | 18 |
Determine whether it is possible to make a journey that starts and finishes at different towns and uses every road exactly once. Give a reason for your answer.
Markscheme and model answer locked
Unlock Question11State1 mark
2026
Six towns are joined by roads. The towns are the vertices A, B, C, D, E and H of a weighted graph, and the lengths of the roads, in kilometres, are shown in the table. A maintenance team has its base at H and must inspect every road.
The team plan to travel along each road exactly once, starting and ending at H.
State a reason why this plan is not possible.
| Road | Length |
|---|---|
| HA | 11 |
| HC | 14 |
| AB | 9 |
| AE | 16 |
| BC | 12 |
| BD | 15 |
| CD | 10 |
| CE | 13 |
| DE | 8 |
The team plan to travel along each road exactly once, starting and ending at H.
State a reason why this plan is not possible.
Markscheme and model answer locked
Unlock Question12Determine2 marks
2026
Seven villages, A to G, are joined by roads. The table lists each road and its length in kilometres; there are no other roads.
Determine whether it is possible to make a journey that starts and finishes at different villages and uses every road exactly once. Give a reason for your answer.
| Road | AB | AD | AE | BC | BD | CD | CF | CG | DE | DF | EF | EG |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Length (km) | 7 | 13 | 14 | 7 | 10 | 14 | 8 | 13 | 10 | 10 | 4 | 9 |
Determine whether it is possible to make a journey that starts and finishes at different villages and uses every road exactly once. Give a reason for your answer.
Markscheme and model answer locked
Unlock Question13Write down1 mark
2026
The graph W has vertices A, B, C, D, E, F, G and H, which represent delivery depots in a region. The weight of each edge is the driving time, to the nearest minute, between two of them. The road between A and F is being repaired, so edge AF has an unknown weight minutes, where . The edges of W are listed below; there are no other edges.
Write down a Hamiltonian cycle in W.
| Edge | Time (minutes) |
|---|---|
| AB | 5 |
| AF | |
| AG | 13 |
| BC | 4 |
| BD | 9 |
| CD | 6 |
| CH | 10 |
| DE | 7 |
| DH | 5 |
| EF | 8 |
| EG | 11 |
| FG | 4 |
| FH | 12 |
| GH | 6 |
Write down a Hamiltonian cycle in W.
Markscheme and model answer locked
Unlock Question14Write down1 mark
2026
A company has six offices, A, B, C, D, E and F. A manager plans to visit every office. The roads between some pairs of offices, with their lengths in kilometres, are listed.
Write down a Hamiltonian cycle for this graph.
| Road | AB | AE | AF | BC | BE | CD | CE | DE | DF | EF |
|---|---|---|---|---|---|---|---|---|---|---|
| Length (km) | 19 | 33 | 15 | 23 | 11 | 16 | 26 | 13 | 31 | 20 |
Write down a Hamiltonian cycle for this graph.
Markscheme and model answer locked
Unlock Question15State2 marks
2026
The table shows the costs, in euros, of ferry crossings between six islands A, B, C, D, E and F. A blank cell means there is no direct connection. The rows show the departure point and the columns the destination.
State whether or not it is possible to travel from A and return to A using exactly 6 direct connections, visiting each of the other five places exactly once. Justify your answer.
| From \ To | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 60 | 80 | ||||
| B | 60 | 110 | 45 | |||
| C | 110 | 85 | 120 | 95 | ||
| D | 85 | 70 | ||||
| E | 80 | 45 | 120 | |||
| F | 95 | 70 |
State whether or not it is possible to travel from A and return to A using exactly 6 direct connections, visiting each of the other five places exactly once. Justify your answer.
Markscheme and model answer locked
Unlock Question16State2 marks
2026
The table shows the costs, in GBP, of direct train tickets between six towns A, B, C, D, E and F. A blank cell means there is no direct connection. The rows show the departure point and the columns the destination.
State whether or not it is possible to travel from A and return to A using exactly 6 direct connections, visiting each of the other five places exactly once. Justify your answer.
| From \ To | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 40 | 75 | ||||
| B | 40 | 55 | ||||
| C | 65 | 50 | ||||
| D | 75 | 55 | 65 | 90 | 100 | |
| E | 50 | 90 | 80 | |||
| F | 100 | 80 |
State whether or not it is possible to travel from A and return to A using exactly 6 direct connections, visiting each of the other five places exactly once. Justify your answer.
Markscheme and model answer locked
Unlock Question17Write down1 mark
2026
The graph W has vertices A, B, C, D, E, F, G and H, which represent museums in a city. The weight of each edge is the travel time by tram, to the nearest minute, between two of them. The tram line between A and F is being repaired, so edge AF has an unknown weight minutes, where . The edges of W are listed below; there are no other edges.
Write down a Hamiltonian cycle in W.
| Edge | Time (minutes) |
|---|---|
| AB | 4 |
| AF | |
| AH | 12 |
| BC | 5 |
| BH | 8 |
| CD | 7 |
| CE | 11 |
| DE | 4 |
| DG | 9 |
| EF | 10 |
| EG | 6 |
| FG | 7 |
| FH | 9 |
| GH | 5 |
Write down a Hamiltonian cycle in W.
Markscheme and model answer locked
Unlock Question18Explain2 marks
2026
A weighted graph has vertices for five depots: Alder (A), Birch (B), Cedar (C), Dogwood (D), Elm (E). Each edge weight is the driving time, in minutes, of the quickest direct road between two depots. The edges are listed below.
Explain why the graph can be described as "connected", but not "complete".
| Edge | Weight |
|---|---|
| AB | 74 |
| AC | 46 |
| AD | 31 |
| AE | 66 |
| BD | 90 |
| BE | 69 |
| CD | 83 |
| CE | 33 |
| DE | 72 |
Explain why the graph can be described as "connected", but not "complete".
Markscheme and model answer locked
Unlock Question19Find2 marks
2026
In an island group, travel between five ports, A, B, C, D and E, is by ferry. There is one direct route between each of these pairs of ports, and no others: A and C; B and C; B and D; C and D; C and E; D and E. Let the undirected graph represent the routes.
Find a possible Eulerian trail in starting at port A.
Find a possible Eulerian trail in starting at port A.
Markscheme and model answer locked
Unlock Question20Write down1 mark
2026
A network of paths joins the points A, B, C, D and E. The paths and their lengths are listed below, where .
Write down the vertices with odd degree.
| Path | Length (km) |
|---|---|
| AB | 6 |
| AE | 5 |
| BE | 4 |
| CD | 3 |
| CE | 8 |
| DE | 2 |
| BC |
Write down the vertices with odd degree.
Markscheme and model answer locked
Unlock QuestionReady to practice Topic 3.14?
Get instant AI feedback on your answers, view detailed markschemes, and track your progress across all IB Math AI SL topics.