| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Impossibility proofs for degree sequences |
| Difficulty | Standard +0.8 This question requires understanding of fundamental graph theory concepts including the handshaking lemma and systematic enumeration. Part (ii) requires proof of a theoretical result, and part (iii) demands logical reasoning about degree sequences and graph uniqueness—going beyond routine application to require mathematical justification and problem-solving insight. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Any simple graph with 4 vertices and 5 arcs (diagram) | B1 | Vertices need not be labelled. Need not be planar |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The sum of the orders of vertices is twice the number of arcs, and hence is even | M1 | Or: start from null graph and successively add arcs. Each time an arc is added the number of odd vertices is either unchanged or increases or decreases by 2 |
| Hence sum of odd orders must be even, so there must be an even number of odd vertices | A1 | So the number of odd nodes is always even |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 5 arcs \(\Rightarrow\) sum of orders of vertices \(= 10\); simple graph connecting vertices so each vertex has order 1, 2 or 3; \(1+3+3+3=10\) or \(2+2+3+3=10\) | M1 | |
| But \(1+3+3+3\) is not possible since if three vertices have order 3 they are all connected to the fourth vertex so it also has order 3 | A1 | Explaining why \(1+3+3+3\) is not possible |
| With \(2+2+3+3\) the two vertices of order 2 cannot be adjacent, since otherwise two arcs connect the other two vertices so not simple. Hence only one possible graph | A1 | Explaining why there is only one graph with nodes of orders 2, 2, 3, 3 |
# Question 2:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Any simple graph with 4 vertices and 5 arcs (diagram) | B1 | Vertices need not be labelled. Need not be planar |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| The sum of the orders of vertices is twice the number of arcs, and hence is even | M1 | Or: start from null graph and successively add arcs. Each time an arc is added the number of odd vertices is either unchanged or increases or decreases by 2 |
| Hence sum of odd orders must be even, so there must be an even number of odd vertices | A1 | So the number of odd nodes is always even |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| 5 arcs $\Rightarrow$ sum of orders of vertices $= 10$; simple graph connecting vertices so each vertex has order 1, 2 or 3; $1+3+3+3=10$ or $2+2+3+3=10$ | M1 | |
| But $1+3+3+3$ is not possible since if three vertices have order 3 they are all connected to the fourth vertex so it also has order 3 | A1 | Explaining why $1+3+3+3$ is not possible |
| With $2+2+3+3$ the two vertices of order 2 cannot be adjacent, since otherwise two arcs connect the other two vertices so not simple. Hence only one possible graph | A1 | Explaining why there is only one graph with nodes of orders 2, 2, 3, 3 |
---2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.\\
(i) Draw a simple graph that connects four vertices using five arcs.\\
(ii) Explain why, in any graph, there must be an even number of odd vertices.\\
(iii) By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.
\hfill \mbox{\textit{OCR D1 2005 Q2 [6]}}