| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Explain why Eulerian circuit impossible |
| Difficulty | Moderate -0.8 This is a straightforward application of Eulerian circuit theory requiring students to identify odd-degree vertices and recall that an Eulerian circuit exists only when all vertices have even degree. Part (ii) is pure recall of a standard theorem with minimal problem-solving, making it easier than average A-level questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| (i) orange – fig; patio – top steps; pool – pool door – back door; front door – garage; front steps – gate – olive | M1, A1 | 12 vertices; connectivity (all 18 arcs and no extras) |
| (ii) 4 ( or ">2" or "multiple" ... not "some") odd nodes ... top steps, pool, front steps, olive ... so neither Eulerian nor semi-Eulerian, but not just "not Eulerian". (This terminology not required.) | B1 | |
| (iii) start/end at pool/top steps, or vice versa; e.g. po–pd-fd-fo-pa-pd-bd-fd-fs-gat-ol-fs-ol-gar-bd-pa-ts-fi-or-ts (20 nodes, 19 arcs); path from front steps to the olive tree | M1, A1, B1 | must be stated |
| (iv) Possible answer: No repetition of any arc needed; Start/stop are front steps/olive | M1, A1 | Alternative answer: By repeating fs/ol or ol/fs ... can start and stop at same point, e.g. front door. |
**(i)** orange – fig; patio – top steps; pool – pool door – back door; front door – garage; front steps – gate – olive | M1, A1 | 12 vertices; connectivity (all 18 arcs and no extras)
**(ii)** 4 ( or ">2" or "multiple" ... not "some") odd nodes ... top steps, pool, front steps, olive ... so neither Eulerian nor semi-Eulerian, but not just "not Eulerian". (This terminology not required.) | B1 |
**(iii)** start/end at pool/top steps, or vice versa; e.g. po–pd-fd-fo-pa-pd-bd-fd-fs-gat-ol-fs-ol-gar-bd-pa-ts-fi-or-ts (20 nodes, 19 arcs); path from front steps to the olive tree | M1, A1, B1 | must be stated
**(iv)** Possible answer: No repetition of any arc needed; Start/stop are front steps/olive | M1, A1 | Alternative answer: By repeating fs/ol or ol/fs ... can start and stop at same point, e.g. front door. | (M1), (A1) |1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths.\\
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}\\
(i) Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths.
Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2]
Joanna, the householder, wants to walk along all of the paths.\\
(ii) Explain why she cannot do this without repeating at least one path.\\
(iii) Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated.
Joanna has a new path constructed which links the pool directly to the top steps.\\
(iv) Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)
\hfill \mbox{\textit{OCR MEI D1 2014 Q1 [8]}}