| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Graph isomorphism |
| Difficulty | Moderate -0.8 This is a straightforward D1 question testing basic graph theory definitions. Part (i) requires constructing simple graphs with given degree sequence (routine but requires care), and part (ii) only needs recall of the Eulerian graph condition (all vertices must have even degree). No problem-solving or proof required, just application of standard definitions. |
| 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 |
| Graph \(A\), Graph \(B\), Graph \(C\) (as shown) | M1, A1 [2] | For a reasonable attempt; For a graph topologically equivalent to one of these graphs |
| Second graph | M1, A1 [2] | For a different reasonable attempt; For a graph topologically equivalent to one of these graphs |
| Third graph | M1, A1 [2] | For another different reasonable attempt; For a graph topologically equivalent to one of these graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The graphs each have four odd nodes, but Eulerian graphs have no odd nodes. | B1 [1] | For any recognition that the nodes are not all even |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Graph $A$, Graph $B$, Graph $C$ (as shown) | M1, A1 [2] | For a reasonable attempt; For a graph topologically equivalent to one of these graphs |
| Second graph | M1, A1 [2] | For a different reasonable attempt; For a graph topologically equivalent to one of these graphs |
| Third graph | M1, A1 [2] | For another different reasonable attempt; For a graph topologically equivalent to one of these graphs |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The graphs each have four **odd** nodes, but Eulerian graphs have no odd nodes. | B1 [1] | For any recognition that the nodes are not all even |
---2 (i) Draw three mathematically different graphs, labelled graph $A$, graph $B$ and graph $C$, each with four vertices, of orders 1, 3, 3 and 3, and five arcs.\\
(ii) Explain how you know that none of the graphs from part (i) is Eulerian.
\hfill \mbox{\textit{OCR D1 2006 Q2 [7]}}