| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This question tests basic graph theory definitions and properties (handshaking lemma, simple connectivity constraints) through straightforward application. Part (i) involves direct calculation and logical deduction from definitions, while parts (ii) and (iii) require drawing examples that satisfy given constraints—routine exercises for D1 students with no novel problem-solving required. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks |
|---|---|
| Answer: \(9 \times 2 = 18\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Since the graph is simple, the two nodes of order 5 are each connected to every other node and hence every node has order at least 2 (exactly 2) | B1 | Explicitly using the fact that the graph is simple. Deducing that each node has order at least 2 or that all other nodes have order 2. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(3 \times 5 = 15\) and \(18 - 15 = 3\). So the orders of the other nodes must sum to at least \(3 \times 3 = 9\) (must sum to more than 3) | B1, B1 | But there are only 9 arcs available. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: A simply connected graph with 6 nodes and 9 arcs, with at least one odd node | M1, A1 | For such a graph with node orders 1, 3, 3, 3, 3, 5. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: A simply connected graph with 6 nodes and 9 arcs, with at least one even node | M1, A1 | For such a graph with node orders 2, 2, 2, 4, 4, 4. |
**(i) a**
Answer: $9 \times 2 = 18$ | B1 |
**(i) b**
Answer: Since the graph is simple, the two nodes of order 5 are each connected to every other node and hence every node has order at least 2 (exactly 2) | B1 | Explicitly using the fact that the graph is simple. Deducing that each node has order at least 2 or that all other nodes have order 2.
**(i) c**
Answer: $3 \times 5 = 15$ and $18 - 15 = 3$. So the orders of the other nodes must sum to at least $3 \times 3 = 9$ (must sum to more than 3) | B1, B1 | But there are only 9 arcs available.
**(ii)**
Answer: A simply connected graph with 6 nodes and 9 arcs, with at least one odd node | M1, A1 | For such a graph with node orders 1, 3, 3, 3, 3, 5.
**(iii)**
Answer: A simply connected graph with 6 nodes and 9 arcs, with at least one even node | M1, A1 | For such a graph with node orders 2, 2, 2, 4, 4, 4.
**Total: 9**
---3 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 connected, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.\\
(i) A simply connected graph is drawn with 6 vertices and 9 arcs.
\begin{enumerate}[label=(\alph*)]
\item What is the sum of the orders of the vertices?
\item Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
\item Explain why the graph cannot have three vertices of order 5 .\\
(ii) Draw an example of a simply connected graph with 6 vertices and 9 arcs in which one of the vertices has order 5 and all the orders of the vertices are odd numbers.\\
(iii) Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2007 Q3 [9]}}