| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Explain why Eulerian circuit impossible |
| Difficulty | Moderate -0.8 Part (a) requires only recalling that an Eulerian circuit exists iff all vertices have even degree—a direct application of a standard theorem. Parts (b) and (c) are routine Chinese Postman algorithm applications with straightforward pairing and counting. This is a standard D1 textbook exercise with no novel problem-solving required. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(m = 3, 4, 5\) | B1 | For at least two correct values |
| All correct values stated | B1 | A connected graph needs \(\geq m-1\) edges; simple needs \(\leq \frac{m(m-1)}{2}\) edges |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(n = 3, 4, 5, 6\) | B1 | For at least two correct values |
| All correct values stated | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Valid graph drawn with 5 vertices | B1 | Must be Eulerian: all vertices even degree |
| Graph is not Hamiltonian (no Hamiltonian cycle possible) | B1 | Must clearly not contain a Hamiltonian cycle |
# Question 7:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| $m = 3, 4, 5$ | B1 | For at least two correct values |
| All correct values stated | B1 | A connected graph needs $\geq m-1$ edges; simple needs $\leq \frac{m(m-1)}{2}$ edges |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| $n = 3, 4, 5, 6$ | B1 | For at least two correct values |
| All correct values stated | B1 | |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Valid graph drawn with 5 vertices | B1 | Must be Eulerian: all vertices even degree |
| Graph is not Hamiltonian (no Hamiltonian cycle possible) | B1 | Must clearly not contain a Hamiltonian cycle |
---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]{194d16e0-8e05-45c0-8948-99808440ed2a-007_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 Q7}}