| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Vertex degree sequences |
| Difficulty | Moderate -0.3 This is a straightforward graph theory question testing basic definitions and the handshaking lemma. Part (i) requires drawing a simple graph and applying the sum-of-degrees formula (routine calculation), while part (ii) asks for enumeration of small graphs—systematic but not conceptually demanding. Slightly easier than average due to small graph sizes and standard textbook concepts. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.
\begin{enumerate}[label=(\roman*)]
\item (a) Draw a simply connected graph that has exactly four vertices and exactly five arcs. Is your graph Eulerian, semi-Eulerian or neither? Explain how you know.\\
(b) By considering the sum of the vertex orders, show that there is only one possible simply connected graph with exactly four vertices and exactly five arcs.
\item Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2014 Q2 [11]}}