| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | November |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Moderate -0.8 This question tests basic definitions and understanding of planarity concepts rather than problem-solving. Part (a) requires recall of standard definitions. Part (b)(i) asks for a simple drawing of K₃,₂ (a small bipartite graph that's trivially planar). Part (b)(ii) requires knowing that the planarity algorithm requires a Hamiltonian cycle, which K₃,₂ lacks—this is recall of algorithm prerequisites rather than application. Overall, this is easier than average A-level maths questions as it's primarily definitional with minimal calculation or reasoning. |
| Spec | 7.02h Hamiltonian paths: and cycles7.02l Planar graphs: planarity, subdivision, contraction |
2. (a) Define the following terms
\begin{enumerate}[label=(\roman*)]
\item planar graph,
\item Hamiltonian cycle.\\
(b) (i) Draw a graph of $\mathrm { K } _ { 3,2 }$ in such a way as to show that it is planar.
\item Explain why the planarity algorithm cannot be used when drawing $\mathrm { K } _ { 3,2 }$ as a planar graph.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q2 [6]}}