| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward D1 graph theory question testing standard definitions and algorithms. Part (a) requires identifying a Hamiltonian cycle by inspection (routine recall), part (b) applies a bookwork planarity algorithm mechanically, and part (c) uses a simple criterion (likely Kuratowski's theorem or Euler's formula). All parts are direct applications of taught material with no problem-solving insight required, making it easier than average A-level questions. |
| Spec | 7.02h Hamiltonian paths: and cycles7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks |
|---|---|
| \(A \in B \, F \, C \, D \, A\) | M1, A1 |
| Answer | Marks |
|---|---|
| e.g. Cycle drawn as hexagon + at least 1 other arc added to diagram | M1 |
| A1 | at least 2 arcs added to hexagon |
| A1 | c.a.o. |
| Answer | Marks |
|---|---|
| Good explanation: AF or EF come named "inside arc" & named "outside" arc. | B2 |
| B1∧ | AF or EF comes named arc. "close" - bad set B1. If it comes with graph give hint |
## Part (a)
| $A \in B \, F \, C \, D \, A$ | M1, A1 | |
## Part (b)
| e.g. Cycle drawn as hexagon + at least 1 other arc added to diagram | M1 | |
| | A1 | at least 2 arcs added to hexagon |
| | A1 | c.a.o. |
## Part (c)
| Good explanation: AF or EF come named "inside arc" & named "outside" arc. | B2 | |
| | B1∧ | AF or EF comes named arc. "close" - bad set B1. If it comes with graph give hint |
---\includegraphics{figure_1}
\begin{enumerate}[label=(\alph*)]
\item Starting from $A$; write down a Hamiltonian cycle for the graph in Figure 1. [2]
\item Use the planarity algorithm to show that the graph in Figure 1 is planar. [3]
\end{enumerate}
Arcs $AF$ and $EF$ are now added to the graph.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Explain why the new graph is not planar. [2]
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q2 [7]}}