| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Impossibility proofs for degree sequences |
| Difficulty | Standard +0.3 This is a multi-part question testing fundamental graph theory concepts (handshaking lemma, Eulerian paths, simple graphs) with straightforward applications. Part (i) uses the odd vertex sum impossibility, parts (ii-iv) apply standard definitions and theorems. While it requires knowledge of multiple concepts, each part involves direct application of rules rather than problem-solving or proof, making it slightly 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 traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks |
|---|---|
| The sum of vertex orders must be even (equals \(2\times\) number of arcs), but \(1+2+3+4+5=15\) which is odd | B1 |
| Answer | Marks |
|---|---|
| A simply connected graph with 6 vertices needs at least 5 arcs (a tree), but vertex of order 6 requires 6 arcs from one vertex alone, and the graph is not simple (a vertex of order 6 in a simple graph with 6 vertices would need to connect to all others including itself) — vertex of order 6 impossible in a simple graph with 6 vertices (max degree = 5) | B1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Two vertices have odd order (4 and 6... wait — orders 2,2,2,2,4,6: vertices of odd order = none since all even) | M1 | Check odd vertices |
| All vertices have even order, so the graph is Eulerian | A1 |
| Answer | Marks |
|---|---|
| Minimum sum of vertex orders = \(2 \times 5 = 10\) (minimum arcs in a simply connected graph on 6 vertices is 5) | B1 |
| Answer | Marks |
|---|---|
| All vertex orders must be even (and \(\geq 2\)), so vertex orders are all even integers \(\geq 2\) | B1 |
| Answer | Marks |
|---|---|
| Sum of vertex orders \(= 2 \times 10 = 20\); 6 vertices all with even order; each vertex order \(\geq 2\); so all vertex orders \(= 2\) (since \(6\times2=12<20\)) — orders must sum to 20 with 6 even values each \(\geq 2\), e.g. some could be 4 | B1 |
| All vertex orders are even and sum to 20, so possible combinations e.g. four vertices order 2, two vertices order 4, etc. | B1 |
| Answer | Marks |
|---|---|
| Valid simply connected Eulerian graph: 6 vertices, 10 arcs, all even vertex orders, drawn correctly | B1 B1 |
# Question 4:
**(i)**
| The sum of vertex orders must be even (equals $2\times$ number of arcs), but $1+2+3+4+5=15$ which is odd | B1 | |
**(ii)(a)**
| A simply connected graph with 6 vertices needs at least 5 arcs (a tree), but vertex of order 6 requires 6 arcs from one vertex alone, and the graph is not simple (a vertex of order 6 in a simple graph with 6 vertices would need to connect to all others including itself) — vertex of order 6 impossible in a simple graph with 6 vertices (max degree = 5) | B1 B1 | |
**(ii)(b)**
| Two vertices have odd order (4 and 6... wait — orders 2,2,2,2,4,6: vertices of odd order = none since all even) | M1 | Check odd vertices |
| All vertices have even order, so the graph is **Eulerian** | A1 | |
**(iii)(a)**
| Minimum sum of vertex orders = $2 \times 5 = 10$ (minimum arcs in a simply connected graph on 6 vertices is 5) | B1 | |
**(iii)(b)**
| All vertex orders must be even (and $\geq 2$), so vertex orders are all even integers $\geq 2$ | B1 | |
**(iv)(a)**
| Sum of vertex orders $= 2 \times 10 = 20$; 6 vertices all with even order; each vertex order $\geq 2$; so all vertex orders $= 2$ (since $6\times2=12<20$) — orders must sum to 20 with 6 even values each $\geq 2$, e.g. some could be 4 | B1 | |
| All vertex orders are even and sum to 20, so possible combinations e.g. four vertices order 2, two vertices order 4, etc. | B1 | |
**(iv)(b)**
| Valid simply connected Eulerian graph: 6 vertices, 10 arcs, all even vertex orders, drawn correctly | B1 B1 | |
---4 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.
Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.
\begin{enumerate}[label=(\roman*)]
\item State how you know that Molly is wrong.
Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
\item (a) Explain how you know that Holly's graph is not simply connected.\\
(b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is.
Olly has drawn a simply connected graph with exactly six vertices.
\item (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.\\
(b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take?
Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
\item (a) What can you deduce about the vertex orders in Polly's graph?\\
(b) Draw a graph that fits the description of Polly's graph.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2016 Q4 [11]}}