| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Physical space modeling |
| Difficulty | Moderate -0.3 This is a structured D1 graph theory question with clear scaffolding. Students must draw adjacency graphs and their complements for given 3D shapes, then determine chromatic numbers. While it requires spatial visualization and understanding the relationship between graph coloring and face adjacency, the question provides a worked example (cube) and guides students through similar problems step-by-step. The concepts are standard D1 curriculum material, making this slightly easier than average A-level maths questions overall. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02j Isomorphism: of graphs, degree sequences |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Adjacency graph: front–back, front–left, front–right, front–base, back–left, back–right, back–base, left–right, left–base, right–base connected appropriately | B1 | adjacency graph all correct cao |
| Complement graph correct (front–back only connected, base isolated) | B1 | complement graph correct cao |
| So 3 colours are needed | B1 | three colours |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Adjacency graph A with top front, top back, top left, top right, base left, base right, base front, base back all correctly connected | M1 | top front adjacency OK |
| A1 | adjacency graph all correct | |
| Complement graph correct | A1 | complement graph correct cao |
| B: Two disjoint, complementary and complete subgraphs can be identified (in several ways) | M1 | two subgraphs |
| A1 | complete |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Adjacency graph: front–back, front–left, front–right, front–base, back–left, back–right, back–base, left–right, left–base, right–base connected appropriately | B1 | adjacency graph all correct cao |
| Complement graph correct (front–back only connected, base isolated) | B1 | complement graph correct cao |
| So 3 colours are needed | B1 | three colours |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Adjacency graph A with top front, top back, top left, top right, base left, base right, base front, base back all correctly connected | M1 | top front adjacency OK |
| | A1 | adjacency graph all correct |
| Complement graph correct | A1 | complement graph correct cao |
| B: Two disjoint, complementary and complete subgraphs can be identified (in several ways) | M1 | two subgraphs |
| | A1 | complete |
---3 The adjacency graph of a cube\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}\\
is shown.
Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge.\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334}
The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph.\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334}
Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.
\begin{enumerate}[label=(\roman*)]
\item Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid.\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
\item (A) Draw the adjacency graph for an octahedron, and draw its complement.\\
(B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph.\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2016 Q3 [8]}}