| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This question tests basic definitions and properties of graphs (Eulerian graphs, vertex orders, handshaking lemma) through straightforward applications. While multi-part, each component requires only direct recall of definitions or simple deductions (e.g., sum of orders = 2×edges). The drawing tasks are routine exercises with no novel problem-solving required. |
| 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 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Connected graph with three vertices of order 2 and one of order 4 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The only simply connected graph with four vertices and five arcs is \(K_4\) with one arc removed, but this is not Eulerian since (two) odd vertices | M1 | Drawing or describing \(K_4\) with one arc removed, or saying 2, 2, 3, 3 (and no other possibility); or drawing a graph with four vertices each of order 2 and then talking about no way to add the fifth arc; or saying there would have to be a vertex of order 4 (ie 2, 2, 2, 4) |
| Sum of vertex orders \(= 10\), graph is Eulerian so vertex orders must be 2, 2, 2, 4. But then graph cannot be simple | A1 | A reasoned argument addressing both 'sum of vertex orders is 10 and graph is Eulerian' and 'graph is simple' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Sum of vertex orders is twice the number of arcs | B1 | \(2 \times 10 = 20\). Allow 'each arc has two ends' but not 'each arc connects two nodes' (could form a loop) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum \(= 2\) | B1 | Min 2 (not implied from eg 2, 4 6 or from \(2\times8=16\)) |
| Maximum \(= 6\) | M1 | Max 6 (not implied from eg 2, 4 6 or from \(6\times8=48\)) |
| [diagram showing example] | A1 | A simple connected graph with eight vertices, seven of order 2 and one of order 6 (and no others). Note: any odd vertices \(\Rightarrow\) A0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| [diagram showing example] | B1 | A simple connected graph with eight vertices, six of order 2 and two of order 4 (and no others). Note: any odd vertices \(\Rightarrow\) B0 |
# Question 2:
## Part (i)(a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Connected graph with three vertices of order 2 and one of order 4 | B1 | |
## Part (i)(b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The only simply connected graph with four vertices and five arcs is $K_4$ with one arc removed, but this is not Eulerian since (two) odd vertices | M1 | Drawing or describing $K_4$ with one arc removed, or saying 2, 2, 3, 3 (and no other possibility); or drawing a graph with four vertices each of order 2 and then talking about no way to add the fifth arc; or saying there would have to be a vertex of order 4 (ie 2, 2, 2, 4) |
| Sum of vertex orders $= 10$, graph is Eulerian so vertex orders must be 2, 2, 2, 4. But then graph cannot be simple | A1 | A reasoned argument addressing both 'sum of vertex orders is 10 and graph is Eulerian' and 'graph is simple' |
## Part (ii)(a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Sum of vertex orders is twice the number of arcs | B1 | $2 \times 10 = 20$. Allow 'each arc has two ends' but not 'each arc connects two nodes' (could form a loop) |
## Part (ii)(b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum $= 2$ | B1 | Min 2 (not implied from eg 2, 4 6 or from $2\times8=16$) |
| Maximum $= 6$ | M1 | Max 6 (not implied from eg 2, 4 6 or from $6\times8=48$) |
| [diagram showing example] | A1 | A simple connected graph with eight vertices, seven of order 2 and one of order 6 (and no others). Note: any odd vertices $\Rightarrow$ A0 |
## Part (ii)(c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| [diagram showing example] | B1 | A simple connected graph with eight vertices, six of order 2 and two of order 4 (and no others). Note: any odd vertices $\Rightarrow$ B0 |
---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 connected Eulerian graph that has exactly four vertices and five arcs but is not simple.\\
(b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs.
A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
\item (a) Explain how you know that the sum of the vertex orders must be 20 .\\
(b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.\\
(c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2013 Q2 [8]}}