| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Vertex degree sequences |
| Difficulty | Moderate -0.8 This is a straightforward D1 graph theory question testing basic definitions and properties. Part (i) requires drawing a simple graph from a degree sequence (routine construction), part (ii) applies the standard Eulerian path/circuit criteria (direct recall), and part (iii) uses the tree property that sum of degrees equals 2(n-1) (simple verification). All parts are textbook applications with no problem-solving or novel insight required, making this easier than average. |
| 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\\
\begin{enumerate}[label=(\roman*)]
\item Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
\item State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
\item Explain why a graph with five vertices of orders $1,2,2,3$ and 4 cannot be a tree.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2009 Q2 [6]}}