Edexcel IAL Maths
The full notes page in 12 sections · live simulations · practice questions
Press F for full screen · → or click to move on
ExaminerPrep is an independent tutoring service. It has been developed independently from and is not endorsed by the International Baccalaureate Organization. "International Baccalaureate", "IB" and "IB Diploma Programme" are registered trademarks of the IBO, used here for descriptive purposes only.
Pearson Edexcel and Cambridge are trademarks of their owners; ExaminerPrep is not affiliated with any exam board.
Route inspection with 0, 2 or 4 odd vertices: why odd vertices force repeats and how to choose the least total repeat
Route inspection when the route may start and finish at different vertices, including a given start
The travelling salesperson problem: classical and practical versions, and the table of least distances
Upper bounds from the nearest neighbour algorithm
Upper bounds from a minimum spanning tree with shortcuts
Lower bounds from a residual minimum spanning tree, and the optimal tour as an interval
1. Route inspection asks for the shortest route along every arc and back to the start; if every vertex has even degree, its length is simply the total weight of the network.
2. Odd vertices come in pairs, and each pair must be joined by a repeated path: route length = total weight + least total of the repeated paths. With four odd vertices compare all three pairings.
3. Different start and finish: start and finish at two odd vertices and repeat only the shortest path between the other two (nothing if there are only two odd vertices).
4. Travelling salesperson: visit every vertex and return, working from a complete table of least distances; in practice a least distance may pass through other vertices.
5. Upper bounds: nearest neighbour, or 2 × MST improved by shortcuts. Lower bound: delete a vertex, find the MST of the rest, add the two shortest arcs from the deleted vertex.
6. Best bounds: the largest lower bound and the smallest upper bound, then lower ≤ optimal ≤ upper.
A gritter that must drive along every street and a sales rep who must call at every town face different problems. The gritter needs a route covering every arc; the rep needs a tour visiting every vertex. D1 solves the first exactly and bounds the second from above and below.
The route inspection problem (Chinese postman problem): find the shortest route that travels along every arc at least once and returns to its starting vertex. Contexts: gritting or sweeping every road, checking every pipe, painting every line on a court.
Every time a route passes through a vertex it uses two arcs there, one in and one out, so a closed route uses an even number of arc-ends at every vertex. If every degree is even the network is Eulerian, and the length is just the total weight. An odd vertex cannot be balanced by the arcs that are there, so some arcs must be travelled twice. Repeating a path between two odd vertices adds one arc-end at each of them and two at every vertex in between, making both even. Since the degrees add to twice the number of arcs, the number of odd vertices is always even: 0, 2, 4, …
Route length = total weight of all arcs + least total weight of the repeated paths. 0 odd vertices: nothing repeated · 2 odd vertices: repeat the shortest path between them · 4 odd vertices: repeat the pair of shortest paths with the least total (three pairings). The shortest path between two odd vertices may go through other vertices; find it by inspection or with Dijkstra.
WORKED EXAMPLE · QUESTION
A park has footpaths AB (7), AC (5), BC (4), BD (8), CD (10), CE (9), DE (6), DF (5) and EF (3), in hundreds of metres. A warden must walk every path, starting and finishing at the gate A. (a) Find the degree of each vertex and explain why some paths must be walked twice. (b) Find the length of the shortest route and state which paths are walked twice. (c) How many times does the route pass through C?
SOLUTION
(a) A 2, B 3, C 4, D 4, E 3, F 2 (sum 18 = 2 × 9 arcs). B and E are odd, so the network is not Eulerian and a closed route must repeat some paths.
(b) Paths from B to E: BCE = 4 + 9 = 13; BDE = 8 + 6 = 14; BDFE = 8 + 5 + 3 = 16. Total = 7 + 5 + 4 + 8 + 10 + 9 + 6 + 5 + 3 = 57, so route = 57 + 13 = 70 (7000 m), with BC and CE walked twice.
(c) C now has 4 + 2 = 6 arc-ends, used two per visit, so 3 times. One possible route: A B C E D B C D F E C A; any route with the right length and arc counts will do.
Common error
Repeating the direct arc between two odd vertices without checking for a shorter indirect path, or adding the repeat to the wrong total. List the possible paths with lengths, choose the least, and write "total + repeat = route length" on one line.
Four odd vertices P, Q, R, S must be joined in two pairs, and there are exactly three ways: PQ + RS, PR + QS, PS + QR. A quick way to list them is to fix the first odd vertex and pair it with each of the others in turn. For each pairing find the shortest path for each pair and add them; list all three, even if one looks obviously best, because the working is part of the answer. Repeat the pairing with the least total.
WORKED EXAMPLE · QUESTION
Cycle lanes have arcs AB (9), AD (7), AG (15), BC (8), BD (10), BE (11), CE (6), CF (9), DE (8), DG (9), EF (5), EG (7) and FG (11), in km, total 115 km. A sweeper must travel every lane, starting and finishing at its depot D. (a) Identify the odd vertices. (b) Find the length of the shortest route, stating the arcs repeated. (c) How many times does the sweeper pass through B?
SOLUTION
(a) A 3, B 4, C 3, D 4, E 5, F 3, G 4, so A, C, E, F are odd.
(b) AC + EF = 17 (ABC) + 5 = 22; AE + CF = 15 (ADE) + 9 = 24; AF + CE = 20 (ADEF) + 6 = 26. Repeat AB, BC and EF: route = 115 + 22 = 137 km.
(c) B has degree 4 and gains 2 (AB and BC repeated): 6 arc-ends, so 3 times. The depot D is even and plays no special part: a closed route has the same length from any start.
Exam tip
Set the pairings out as three lines, each "pair + pair = total", with the route of any indirect path in brackets. It shows the comparison the question is testing, and a slip in one path is easy to spot.
If the route need not return, the start and finish may keep odd degree: the route leaves the start once more than it arrives, and arrives at the finish once more than it leaves.
Two odd vertices: start at one, finish at the other, and repeat nothing: the network is semi-Eulerian, and the length is the total weight.
Four odd vertices: two can be the start and finish, so only the other two need joining. Repeat the single shortest path between any two of the four, and start and finish at the remaining two. That means comparing all six paths, not the three pairings.
Start fixed at an odd vertex: only three options remain: finish at each other odd vertex in turn, repeating the path between the two that are left.
WORKED EXAMPLE · QUESTION
For the cycle lanes of worked example 2 (total 115 km, odd vertices A, C, E, F), the sweeper no longer has to return to its depot. (a) Find the shortest route length and where it should start and finish. (b) The sweeper must now start at E. Where should it finish, and how long is the route?
SOLUTION
(a) Shortest paths: AC 17, AE 15, AF 20, CE 6, CF 9, EF 5. Repeat the least: 115 + 5 = 120 km, from A to C (or the reverse).
(b) Finish A: repeat CF = 9, giving 124; finish C: repeat AF = 20, giving 135; finish F: repeat AC = 17, giving 132. Finish at A; 124 km. Fixing the start costs 4 km, because E is one end of EF, the cheapest path that would otherwise be repeated.
Common error
Using the least pairing total (22) for an open route. With a different start and finish only one path is repeated, so repeat the shortest of the six (5).
The travelling salesperson problem (TSP): find the shortest route that visits every vertex and returns to the start. A tour is a cycle through all the vertices. In the classical problem each vertex is visited exactly once (a Hamiltonian cycle); in the practical problem each vertex is visited at least once, so passing through a vertex again is allowed if quicker.
No efficient algorithm is known that always finds the optimal tour for large networks: the number of tours grows factorially. D1 therefore finds an upper and a lower bound. To turn a practical problem into a classical one, replace the network by a complete table of least distances: every pair of vertices with the length of the shortest path between them. The table satisfies the triangle inequality (going direct is never longer than going via a third vertex). After solving, interpret any entry that is not a direct arc: that step passes through other vertices.
WORKED EXAMPLE · QUESTION
Towns A–F are joined by roads AB (13), AC (9), AD (21), BC (8), BE (11), CD (14), CE (16), DE (7), DF (10) and EF (12), in km. Complete the table of least distances, explaining any entry that is not a direct road.
SOLUTION
Copy the direct roads, checking none is beaten by a route through another town (AD: direct 21, via C 23, so 21 stays). Then fill the gaps: AE = 24 (A–B–E; A–C–E is 25); AF = 31 (A–D–F; A–C–D–F is 33); BD = 18 (B–E–D); BF = 23 (B–E–F); CF = 24 (C–D–F).
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 13 | 9 | 21 | 24 | 31 |
| B | 13 | — | 8 | 18 | 11 | 23 |
| C | 9 | 8 | — | 14 | 16 | 24 |
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| D | 21 | 18 | 14 | — | 7 | 10 |
| E | 24 | 11 | 16 | 7 | — | 12 |
| F | 31 | 23 | 24 | 10 | 12 | — |
Bold entries are not direct roads; a tour using one passes through another town.
The nearest neighbour algorithm
Choose a start vertex; repeatedly move to the nearest vertex not yet visited; when all are visited, return to the start. The result is a genuine tour, so the optimal tour is no longer: its length is an upper bound. Use the table of least distances so every vertex can be reached at every step (on the original network the algorithm can get stuck or fail to return). Different starts usually give different tours; the best upper bound is the smallest. Greedy choices can force an expensive final step, which is why the bound is often well above the optimum.
WORKED EXAMPLE · QUESTION
Using the table in worked example 4: (a) apply nearest neighbour from A to find an upper bound; (b) interpret the tour on the road network; (c) repeat (a) from B and state the better upper bound.
SOLUTION
(a) A → C (9) → B (8) → E (11) → D (7) → F (10) → A (31): upper bound 76 km.
(b) F → A is A–D–F reversed, so the route is A C B E D F D A (D visited twice).
(c) B → C (8) → A (9) → D (21) → E (7) → F (12) → B (23) = 80 km. Better upper bound 76 km. At C (from B) the nearest unvisited town is A (9), not D (14): read the whole row and ignore towns already visited.
A minimum spanning tree with shortcuts
Walking all the way round a minimum spanning tree and back uses every tree arc twice and visits every vertex, so 2 × MST weight is an upper bound. That walk revisits vertices. A shortcut jumps straight to the next unvisited vertex using the table; by the triangle inequality it is never longer than the arcs it replaces, so shortcuts can only lower the bound. Questions often say "use shortcuts to reduce the upper bound to below …": show the tour and its length.
WORKED EXAMPLE · QUESTION
This six-town table (km) is a classical problem: every entry is already a least distance. (a) Use Prim's algorithm from P to find a minimum spanning tree, listing arcs in order, and state its weight. (b) Hence find an initial upper bound. (c) Use shortcuts to reduce the upper bound below 170 km.
| P | Q | R | S | T | U | |
|---|---|---|---|---|---|---|
| P | — | 33 | 26 | 24 | 43 | 40 |
| Q | 33 | — | 21 | 35 | 30 | 46 |
| R | 26 | 21 | — | 29 | 18 | 31 |
| S | 24 | 35 | 29 | — | 39 | 23 |
| T | 43 | 30 | 18 | 39 | — | 34 |
| U | 40 | 46 | 31 | 23 | 34 | — |
SOLUTION
(a) PS (24), SU (23), PR (26), RT (18), RQ (21): weight 112 km.
(b) 2 × 112 = 224 km (the walk P S U S P R T R Q R P).
(c) U → R replaces U–S–P–R (23 + 24 + 26 = 73) by 31; T → Q replaces T–R–Q (39) by 30; Q → P replaces Q–R–P (47) by 33. Tour P S U R T Q P = 24 + 23 + 31 + 18 + 30 + 33 = 159 km < 170. Branch order matters: P S U R Q T P gives 172 km, which misses the target.
Residual minimum spanning tree method: (1) delete one vertex X and all its arcs; (2) find the MST of the remaining vertices; (3) add the two shortest arcs from X. Each deleted vertex gives a lower bound; the best is the largest.
Why it works: any tour with X removed becomes a path through all the other vertices, which is a spanning tree, so it is at least the residual MST; the tour also uses exactly two arcs at X, which are at least the two shortest. If the residual tree plus the two arcs happens to form a tour, that tour is optimal; likewise if the best lower bound equals an upper bound.
WORKED EXAMPLE · QUESTION
For the six towns of worked example 4: (a) by deleting A, use Kruskal's algorithm on the table to find a lower bound; (b) deleting B instead, find another lower bound; (c) using worked example 5, write down the smallest interval for the optimal tour.
SOLUTION
(a) Kruskal on B–F: DE (7), BC (8), DF (10), BE (11), which already join all five, so residual MST = 36. Add AC = 9 and AB = 13: lower bound 58 km.
(b) Residual MST: DE (7), AC (9), DF (10), CD (14) = 40; add BC = 8 and BE = 11: 59 km.
(c) Largest lower bound 59, smallest upper bound 76: 59 ≤ optimal tour ≤ 76 (km). Checking all 60 tours shows the optimum is 69 km (A B E F D C A), inside the interval; you are never expected to do this.
Common error
Choosing the smallest lower bound ("it is safer") or the largest upper bound. Both are true, but the interval should be as narrow as possible: largest lower bound, smallest upper bound.
A full question starts from a practical network, completes the table of least distances, finds an upper bound, interprets it, finds a lower bound and finishes with an interval. Each step uses the previous one, so keep tables and lists clear.
WORKED EXAMPLE · QUESTION
A technician must visit masts H, J, K, L, M and N, starting and finishing at H. Tracks: HJ (17), HK (23), HN (11), JK (19), JL (8), KL (18), KM (22), LM (13), LN (19), MN (29), in km. Part of the table of least distances:
| H | J | K | L | M | N | |
|---|---|---|---|---|---|---|
| H | — | 17 | 23 | 11 | ||
| J | 17 | — | 19 | 8 | 21 | 27 |
| K | 23 | 19 | — | 18 | 22 | |
| L | 8 | 18 | — | 13 | 19 | |
| M | 21 | 22 | 13 | — | 29 | |
| N | 11 | 27 | 19 | 29 | — |
(a) Find HL, HM and KN, showing the routes. (b) Use nearest neighbour from H to find an upper bound. (c) Interpret the tour on the network. (d) From J, nearest neighbour gives 104 km. State, with a reason, the better upper bound. (e) By deleting L, find a lower bound. (f) Give the smallest interval for the optimal tour.
SOLUTION
(a) HL = 25 (H–J–L; H–N–L is 30, H–K–L is 41); HM = 38 (H–J–L–M); KN = 34 (K–H–N; K–L–N is 37).
(b) H → N (11) → L (19) → J (8) → K (19) → M (22) → H (38): 117 km.
(c) M → H is not a track: use M–L–J–H, so H N L J K M L J H (L and J passed twice).
(d) 104 km, because it is the smaller upper bound (a tour of that length exists).
(e) Kruskal on H, J, K, M, N: HN (11), HJ (17), JK (19), JM (21) = 68; two least from L: LJ = 8, LM = 13: 89 km. JM = 21 is a table entry even though its route passes through L; use the table as written.
(f) 89 ≤ optimal tour ≤ 104 (km). The optimal tour is 101 km, inside the interval.
Exam tip 1 — show every pairing
For four odd vertices, write all three pairings with totals, then state the least and name the repeated arcs. A bare "repeat AB, BC, EF" with no comparison does not show the algorithm.
Exam tip 2 — name the repeated arcs
Routes and visit counts depend on which arcs are repeated, so name them ("AB, BC and EF"), not only the extra length.
Exam tip 3 — upper bound smaller, lower bound larger
"Best" means the narrowest interval. Write the answer as an inequality with units, e.g. 59 ≤ T ≤ 76.
Exam tip 4 — nearest neighbour lists
Write the tour with each step's length (A → C (9) → B (8) …) and the total, so each greedy choice is visible and no vertex is revisited.
Exam tip 5 — interpret table entries in context
When a tour uses a least distance that is not a direct arc, replace the step by the actual path so the vertices passed through appear (F D A, not F A).
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| The repeated path between two odd vertices is the direct arc. | The shortest path may be indirect, or there may be no direct arc (worked example 1 has no BE; B–C–E = 13 beats B–D–E = 14). | Find the shortest path by inspection or Dijkstra. |
| With four odd vertices, repeat the two shortest single paths. | They may share a vertex and not form a pairing, or another pairing may be cheaper. | Compare the totals of the three pairings. |
| An open route still uses the best pairing. | Start and finish can stay odd, so only one path is repeated. | Repeat the shortest of the six paths; start and finish at the other two. |
| The nearest neighbour tour is the optimal tour. | It is greedy and can end with a long return step. | It gives an upper bound only. |
| A lower bound must be the length of a real tour. | The residual tree plus two arcs is usually not a tour. | It shows no tour is shorter; it equals the optimum only if it forms a tour. |
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| Classical and practical problems always have the same answer. | Revisiting vertices can be shorter on the original network. | Solve with the table of least distances, then interpret the tour. |
D1.2 Graphs, minimum spanning trees and Dijkstra
The Eulerian test decides whether anything is repeated; Dijkstra finds shortest paths between odd vertices and builds the table of least distances; Prim and Kruskal give the trees for both bounds.
D1.1 Algorithms
Nearest neighbour is greedy, like first-fit bin packing: fast but not always optimal, and judged against a bound just as a packing is judged against the lower bound for bins.
P1 inequalities, and D1.4–D1.5
The answer is an interval, written with the same care as any inequality. Like the TSP bounds, critical path analysis and linear programming ask you to model, apply an algorithm and interpret the result in context.
| Formula | Use | In the formulae list? |
|---|---|---|
| sum of degrees = 2 × number of arcs | shows the number of odd vertices is even; checks degree counts | No — learn it |
| closed route = total weight + least total of repeated paths | route inspection length (0, 2 or 4 odd vertices) | No — learn it |
| 4 odd vertices: 3 pairings (PQ + RS, PR + QS, PS + QR) | listing the options to compare | No — learn it |
| open route = total weight + shortest single path between odd vertices | start and finish at different vertices (four odd vertices); two odd vertices: total weight | No — derive it |
| times a vertex is passed through = (degree + repeated arc-ends) ÷ 2 | counting visits on a closed route | No — derive it |
| upper bound = 2 × MST weight (then shortcuts) | minimum spanning tree method | No — learn it |
| Formula | Use | In the formulae list? |
|---|---|---|
| lower bound = residual MST + two least arcs from the deleted vertex | residual minimum spanning tree method | No — learn it |
| largest lower bound ≤ optimal tour ≤ smallest upper bound | the interval for the optimal tour | No — learn it |
1. A network has all vertices of even degree and total weight 84. What is the shortest closed route covering every arc?
2. A graph has degrees 3, 3, 3, 3, 2 and 2. How many arcs does it have, and how many pairings must be compared?
3. A route inspection network has odd vertices P and Q only, and the route may start and finish anywhere. Where should it start and finish, and what is repeated?
4. A lower bound of 141 and an upper bound of 141 are found for a travelling salesperson problem. What can you conclude?
5. Why is nearest neighbour usually applied to a table of least distances rather than the original network?
1. 84. The network is Eulerian, so a closed route uses every arc exactly once and nothing is repeated.
2. The degrees add to 16, so 8 arcs. Four odd vertices give three pairings.
3. Start at P and finish at Q (or the reverse). Nothing is repeated: the network is semi-Eulerian, so the length is the total weight.
4. The optimal tour is exactly 141, and the tour giving the upper bound is optimal.
5. On an incomplete network the current vertex may have no arc to an unvisited vertex, or the last vertex no arc back to the start, so the algorithm stalls. The table is complete, so every step is possible.
Check understanding
The answer and each step appear one click at a time.
A canal company inspects every towpath in its network. The towpaths join locks K, L, M, N, P, Q and R and are KL 9, KM 12, LM 18, LN 4, MP 12, NP 15, NQ 14, PQ 14, PR 11 and QR 5 (lengths in km), total 114 km. Each inspection starts and finishes at K.
Figure: the towpaths, lengths in km; not to scale
(a) Use the route inspection algorithm to find the length of the shortest inspection route, stating the towpaths that are inspected twice. [5]
(b) The towpath MP is permanently closed and will no longer be inspected. Find the length of the new shortest inspection route. [4]
Mark scheme click to reveal each step
odd vertices L, M, N, Q
LM + NQ = 18 + 14 = 32; LN + MQ = 4 + 26 (MPQ) = 30
LQ + MN = 18 (LNQ) + 22 (MLN) = 40
repeat LN, MP and PQ
114 + 30 = 144 km
new odd vertices L, N, P, Q (M is now even, P odd)
LN + PQ = 4 + 14 = 18; LP + NQ = 19 (LNP) + 14 = 33; LQ + NP = 18 (LNQ) + 15 = 33
least 18
Figure 1 shows the pipelines between seven pumping stations A to G, with their lengths in km. The total length of the pipelines is 89 km. An engineer must inspect every pipeline, starting and finishing at station A.
(a) Write down the odd vertices of the network. [1]
(b) Use the route inspection algorithm to find the three possible pairings of the odd vertices and the total length of the repeated pipelines for each. [4]
(c) State which pipelines are inspected twice and find the length of the engineer's route. [2]
(d) Write down a possible route for the engineer, starting and finishing at A. [2]
Mark scheme click to reveal each step
B, C, E and F
a correct pairing with shortest paths attempted
BC + EF = 12 (BGC) + 12 = 24
BE + CF = 12 (BGE) + 14 (CGF) = 26
BF + CE = 16 (BGF) + 10 (CGE) = 26
BG, GC and EF
89 + 24 = 113 km
a closed route of 13 arcs using BG, GC and EF twice and every other pipeline once
Keep practising
Full notes, every simulation and hundreds of questions with mark schemes, free:
ExaminerPrep is an independent tutoring service. It has been developed independently from and is not endorsed by the International Baccalaureate Organization. "International Baccalaureate", "IB" and "IB Diploma Programme" are registered trademarks of the IBO, used here for descriptive purposes only.
Pearson Edexcel and Cambridge are trademarks of their owners; ExaminerPrep is not affiliated with any exam board.