| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Explain why Eulerian circuit impossible |
| Difficulty | Moderate -0.5 Part (a) requires only stating that vertices have odd degree (standard Eulerian circuit criterion recall). Parts (b-c) involve routine Chinese Postman algorithm application—identifying odd vertices, finding minimum pairings, and counting passes. This is a textbook D1 question with straightforward application of standard algorithms, making it slightly easier than average A-level maths overall. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd vertices at \(A, B, C, I\) | E1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(AB + CI = 100 + 440 = 540\) | M1 | |
| \(AC + BI = 150 + 450 = 600\) | A2,1,0 | |
| \(AI + BC = 380 + 120 = 500\) | ||
| Repeat \(AI + BC\) | E1 | May be implied |
| Distance \(2090 + 500 = 2590\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route with \((3A), 2B, 2C, 3D, 2E, 2F, 3G, 1H, 2I, 1J\) | M1 | \(16 \to 21\) |
| \(= 18\) | A1 |
## Question 7:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd vertices at $A, B, C, I$ | E1 | |
**Total: 1 mark**
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $AB + CI = 100 + 440 = 540$ | M1 | |
| $AC + BI = 150 + 450 = 600$ | A2,1,0 | |
| $AI + BC = 380 + 120 = 500$ | | |
| Repeat $AI + BC$ | E1 | May be implied |
| Distance $2090 + 500 = 2590$ | B1 | |
**Total: 5 marks**
### Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route with $(3A), 2B, 2C, 3D, 2E, 2F, 3G, 1H, 2I, 1J$ | M1 | $16 \to 21$ |
| $= 18$ | A1 | |
**Total: 2 marks**7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station.\\
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_1539_1162_495_424}
Stella leaves the bus station at $A$. She decides to walk along all of the roads at least once before returning to $A$.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to start from $A$, travel along each road only once and return to $A$.
\item Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at $A$.
\item At each of the 9 places $B , C , \ldots , J$, there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q7 [13]}}