| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Game and interaction modeling |
| Difficulty | Standard +0.3 This is a straightforward application of the handshaking lemma and pigeonhole principle in graph theory. Part (i) is routine graph construction, part (ii) requires recognizing that someone shaking 0 hands contradicts someone shaking hands with all 3 others, and part (iii) is a standard pigeonhole argument. While it requires understanding basic graph theory concepts, the reasoning is guided and doesn't demand novel insight—slightly easier than average for A-level. |
| Spec | 7.01c Pigeonhole principle7.02a Graphs: vertices (nodes) and arcs (edges) |
1 Alfred, Ben, Charles and David meet, and some handshaking takes place.
\begin{itemize}
\item Alfred shakes hands with David.
\item Ben shakes hands with Charles and David.
\item Charles shakes hands with Ben and David.\\
(i) Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.\\
(ii) Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .\\
(iii) Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.
\end{itemize}
\hfill \mbox{\textit{OCR MEI D1 2009 Q1 [8]}}