| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Abstract shape and algorithm modeling |
| Difficulty | Standard +0.8 This question requires understanding of a non-standard graph coloring technique (Kempe chains) not typically covered in basic graph theory, plus abstract reasoning about what constitutes an algorithm. Part (i) demands careful visualization of subgraphs and strategic color swapping, while part (ii) requires metacognitive understanding of algorithmic properties—both going beyond routine D1 exercises. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges) |
2 The vertices of a graph are to be coloured using the following rules:
\begin{itemize}
\item all vertices are to be coloured
\item no two vertices joined by an edge are to have the same colour.
\end{itemize}
The following graph has been coloured with four colours.\\
\includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-2_357_883_1683_591}
Kempe's rule allows for colours to be swapped. The rule is:
\begin{itemize}
\item choose two colours
\item draw the subgraph consisting of the vertices coloured with these two colours, together with the edges that connect them
\item in any connected part of this subgraph consisting of two or more vertices, the two colours can be swapped.\\
(i) Use Kempe's rule, choosing the colours blue and red.
\end{itemize}
Show that the graph can then be coloured with two colours.\\
(ii) Why does Kempe's rule not constitute an algorithm for colouring graphs?
\hfill \mbox{\textit{OCR MEI D1 2010 Q2 [8]}}