| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2021 |
| Session | June |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Standard +0.8 This requires applying the planarity algorithm systematically to a specific graph after finding a Hamiltonian cycle. While the algorithm itself is mechanical, students must correctly complete the cycle, then carefully track which edges are inside/outside while checking for conflicts. The multi-step nature and need for systematic organization make this moderately challenging, though it's a standard FP1/FD1 application rather than requiring novel insight. |
| Spec | 7.02h Hamiltonian paths: and cycles7.02l Planar graphs: planarity, subdivision, contraction7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(\ldots, D, Y, B, U, C\) | B1 | CAO (CVEXAWDYBUC) – must return to C |
| (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Draw Hamiltonian cycle as polygon edges with remaining arcs shown intersecting inside; OR list arcs not part of Hamiltonian cycle: AU, AV, BV, CW, CX, DX, EY | M1 | Either draws Hamiltonian cycle from (a) as edges of a polygon showing remaining arcs intersecting inside, OR lists arcs not part of the Hamiltonian cycle |
| Select any arc not part of Hamiltonian cycle and list correct intersecting arcs (e.g. AU(I) intersects BV, EY, CW, DX → label as AU(I), AV, BV(O), CW(O), CX, DX(O), EY(O)) | A1 | Dependent on correct Hamiltonian cycle and correct arcs not part of cycle |
| Edges BV and CW intersect, so graph is not planar | A1 | cao – states two unlabelled (or same-labelled) arcs which intersect each other and concludes graph is not planar. Dependent on correct Hamiltonian cycle in (a) or (b) |
| (3) |
# Question 1:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $\ldots, D, Y, B, U, C$ | B1 | CAO (CVEXAWDYBUC) – must return to C |
| | **(1)** | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Draw Hamiltonian cycle as polygon edges with remaining arcs shown intersecting inside; OR list arcs not part of Hamiltonian cycle: AU, AV, BV, CW, CX, DX, EY | M1 | Either draws Hamiltonian cycle from (a) as edges of a polygon showing remaining arcs intersecting inside, OR lists arcs not part of the Hamiltonian cycle |
| Select any arc not part of Hamiltonian cycle and list correct intersecting arcs (e.g. AU(I) intersects BV, EY, CW, DX → label as AU(I), AV, BV(O), CW(O), CX, DX(O), EY(O)) | A1 | Dependent on correct Hamiltonian cycle and correct arcs not part of cycle |
| Edges BV and CW intersect, so graph is not planar | A1 | cao – states two unlabelled (or same-labelled) arcs which intersect each other **and** concludes graph is not planar. Dependent on correct Hamiltonian cycle in (a) or (b) |
| | **(3)** | |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-02_606_670_260_699}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
A Hamiltonian cycle for the graph in Figure 1 begins $\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots$.
\begin{enumerate}[label=(\alph*)]
\item Complete the Hamiltonian cycle.
\item Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2021 Q1 [4]}}