| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | November |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Standard +0.3 This is a straightforward application of a standard D1 algorithm (planarity testing via Hamiltonian cycle). Students need to complete a partially-given Hamilton cycle and then mechanically apply the planarity algorithm. While it requires careful execution, it's a routine textbook procedure with no novel problem-solving or insight required, making it slightly easier than average. |
| Spec | 7.02h Hamiltonian paths: and cycles7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
\begin{enumerate}
\item Figure 1\\
\includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}
\end{enumerate}
A Hamilton cycle for the graph in Fig. 1 begins $A , X , D , V , \ldots$.\\
(a) Complete this Hamiltonian cycle.\\
(b) Hence use the planarity algorithm to determine if the graph is planar.\\
\hfill \mbox{\textit{Edexcel D1 2002 Q1 [4]}}