| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 7 |
| 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 standard D1 algorithms: finding a Hamiltonian cycle (systematic trial) and then using it to construct a planar drawing. Both are routine procedures taught explicitly in the specification with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.02h Hamiltonian paths: and cycles7.02m Euler's formula: V + R = E + 2 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) e.g. ABCDFEA | B2 | |
| (b) Start with AC on inside, move BD outside, giving plane drawing | M3 A2 | (7) |
**(a)** e.g. ABCDFEA | B2 |
**(b)** Start with AC on inside, move BD outside, giving plane drawing | M3 A2 | (7)
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-02_629_700_196_443}
\captionsetup{labelformat=empty}
\caption{Fig 1}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Find a Hamiltonian cycle for the graph shown in Figure 1.
\item Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.\\
(5 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q1 [7]}}