| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Session | Specimen |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Easy -1.2 This question tests basic definitions and properties of complete graphs at an introductory level. Part (i) requires drawing K₅ and recalling that a graph is Eulerian if all vertices have even degree (straightforward to verify). Parts (ii) and (iii) simply ask for examples of a path and cycle by listing arcs—pure recall with no problem-solving. This is easier than average A-level content, comparable to routine bookwork in early modules. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | Draw K₅ with all 10 arcs connecting 5 nodes; every node has degree 4 (even), so it is Eulerian | B1 (diagram), B1 (reason: all nodes have even degree) |
| (ii) | Any valid path using more than one arc, e.g. AB, BC | B1 |
| (iii) | Any valid cycle, e.g. AB, BC, CA | B1 |
# Question 1:
**(i)** | Draw K₅ with all 10 arcs connecting 5 nodes; every node has degree 4 (even), so it is Eulerian | B1 (diagram), B1 (reason: all nodes have even degree) | Must state all nodes have even/degree 4
**(ii)** | Any valid path using more than one arc, e.g. AB, BC | B1 | Must list arcs, not nodes; path must not repeat a node
**(iii)** | Any valid cycle, e.g. AB, BC, CA | B1 | Must list arcs; start and end at same node
---1 The graph $\mathrm { K } _ { 5 }$ has five nodes, $A , B , C , D$ and $E$, and there is an arc joining every node to every other node.\\
(i) Draw the graph $\mathrm { K } _ { 5 }$ and state how you know that it is Eulerian.\\
(ii) By listing the arcs involved, give an example of a path in $\mathrm { K } _ { 5 }$. (Your path must include more than one arc.)\\
(iii) By listing the arcs involved, give an example of a cycle in $\mathrm { K } _ { 5 }$.
\hfill \mbox{\textit{OCR D1 Q1 [4]}}