Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7367Paper 3 · Discrete optionNetworksRoute inspection and TSP

Networks · Subtopic 3 of 3

Route Inspection and the Travelling Salesperson

To travel every edge and return, you must repeat edges between odd vertices. Pair the odd vertices to minimise the extra distance; route length $=$ total weight $+$ that extra. For visiting every vertex (TSP), bound the answer: nearest neighbour gives an upper bound; deleted vertex (MST of the rest $+$ two cheapest edges) gives a lower bound.

Edexcel YMA01 WDM11Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Solve route inspection problems with 2 or 4 odd vertices.
Adapt when start and finish may differ.
Find upper and lower bounds for the travelling salesperson problem.

Pause and think

A gritter must drive every street in a village and return to the depot. Why might some streets be driven twice?

Section 2 of 14

Core idea

Start hereThe postman’s round

A postman must walk down every street and return to the depot. If every junction had an even number of streets, he'd never repeat one. Odd junctions force repeats. The question is which repeats are cheapest.

The big idea

Pair the odd vertices so that the total of the shortest paths between partners is least. Repeating those paths makes every degree even, so an Eulerian circuit exists. Route length $=$ total weight $+$ added paths.

1. Route inspection

Network used below: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .

Worked exampleTwo odd vertices

Find the shortest closed route traversing every edge.

Goal: Length.
Strategy: Find odd vertices and the shortest path between them.

$\text{degrees }A2,B3,C4,D3,E2$
Tabulate.
$\text{odd: }B,D;\ \text{shortest }BD=5$
Direct edge beats $BCD=8$ .
$30+5=35$
Total weight plus repeat.

Answer

35

✓ CheckAfter repeating

BD

, all degrees even ✓.

Counting pairings

$4\text{ odd: first vertex has }3\text{ partners}$
The other two are then forced.
$6\text{ odd: }5\times3\times1=15$
Pick a partner for the first, then repeat on four.

2k

odd vertices give

(2k-1)(2k-3)\cdots1

pairings.

2. Travelling salesperson bounds

Worked exampleDeleted-vertex lower bound

Removing $A$ leaves an MST of weight $10$ ; the two cheapest edges at $A$ are $3$ and $4$ . Find a lower bound.

Goal: Bound.
Strategy: MST of the rest $+$ two cheapest edges at the deleted vertex.

$10+3+4$
A tour uses two edges at $A$ and spans the rest.
$=17$
Add.

AnswerLower bound

17

; optimal tour

\ge17

✓ CheckShould be below any nearest-neighbour tour length ✓.

TSP bounds

Drawing diagram…

The optimum is trapped between the bounds.

TrickOpen routes If start and finish may differ, don't repeat the pairing with the largest path; start and end at those two vertices.

Common misconceptionShortest paths The repeated path between two odd vertices may go through other vertices; use the shortest path, not the direct edge.

Pause and think

How long is the shortest route in the network if you can finish anywhere?

Summary

Pair odd vertices; repeat cheapest paths.
Route $=$ total $+$ repeats.
TSP: lower $\le$ optimal $\le$ upper.

Route inspection: Shortest closed route using every edge.
Travelling salesperson: Shortest tour visiting every vertex.

HistoryMeigu Guan. Chinese mathematician Meigu Guan (Kwan Mei-Ko) solved the postman's problem in 1960 while studying postal delivery, hence "Chinese postman".

Fun factTSP records. The largest TSP solved exactly visits 85,900 points (computer chip layout), taking over 136 CPU-years.

Section 3 of 14

Key formulae

Route inspection

\text{route}=\sum\text{weights}+\min\text{(pairing total)}

Pairings

2\text{ odd}:1;\quad4\text{ odd}:3;\quad6\text{ odd}:15

TSP bounds

\text{lower bound}\le\text{optimal}\le\text{upper bound}

TrickDifferent start and finish. If you may finish elsewhere, leave the pair of odd vertices with the longest connecting path unrepeated, and start and end there.

Section 4 of 14

Worked examples

Example 1 · Two odd vertices0 / 3 steps

In the network (

AB4

AC3

BC2

BD5

CD6

CE7

DE3

), find the shortest inspection route from

A

back to

A

Section 5 of 14

Explore the graph

The example network

Loading the interactive graph…

Try this

Vertices: $A(0,2)$ , $B(2,4)$ , $C(2,0)$ , $D(4,4)$ , $E(5,1)$ . Weights: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .
$B$ and $D$ have degree 3; repeating $BD$ makes every degree even.

Route length $30+5=35$ .

In the real worldBin lorries. Councils plan refuse and gritting rounds with route-inspection software to cut repeated mileage.

Section 6 of 14

Common mistakes

IncorrectUsing the direct edge when a shorter path exists

CorrectUse the shortest path

Repeat whichever route is cheapest.

IncorrectMissing a pairing

CorrectList all 3 for four odd vertices

AB/CD

AC/BD

AD/BC

IncorrectLower bound bigger than upper

CorrectRecheck

Bounds must sandwich the optimum.

Postman: every street once

Odd vertices: absolutely not.

Section 7 of 14

Exam tip

Exam tipWrite pairings in full. Show each pairing with both path lengths and the total; examiners need to see the comparison.

Section 8 of 14

Guided practice

SA-DM-RI-G011 markL1 FoundationNon-calculatorRoute inspection

Find the total weight of the network

AB4

AC3

BC2

BD5

CD6

CE7

DE3

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-RI-0012 marksL2 StandardNon-calculatorRoute inspection

Find the length of the shortest closed route that traverses every edge of that network.

Salam Academy Original Practice · Proposed mark scheme

SA-DM-RI-0021 markL1 FoundationNon-calculatorRoute inspection

How many ways can six odd vertices be paired?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-RI-0032 marksL2 StandardNon-calculatorTSP bounds

For a TSP, deleting vertex

A

leaves an MST of weight

10

. The two shortest edges from

A

are

3

and

4

. Find the lower bound.

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-RI-0042 marksL3 ExamNon-calculatorRoute inspection

In the same network, the route must traverse every edge but may start and finish at different vertices. Find the shortest length.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Pair odd vertices; repeat cheapest paths.
Route $=$ total $+$ extra.
TSP: nearest neighbour (upper), deleted vertex (lower).

Section 12 of 14

Quick quiz

Q1 · SA-DM-RI-Q011 markL1 FoundationNon-calculatorTSP bounds

The nearest neighbour algorithm for the TSP gives

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7367 A-level Further Mathematics
Where: Discrete · Networks
Expected: Route inspection; travelling salesperson upper and lower bounds.
Calculator: Permitted on all papers.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7367 · Paper 3

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7367, First teaching 2017 (official specification).