| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Session | Specimen |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Standard +0.8 This question requires applying the planarity algorithm systematically to a specific graph with a given Hamiltonian cycle, which is a multi-step procedure requiring careful tracking of arc classifications (inside/outside/undecided) and logical reasoning. While the algorithm itself is mechanical, correct application demands precision and understanding beyond simple recall, placing it moderately above average difficulty for A-level. |
| 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 | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A planar graph is a graph that can be drawn so that... | B1 | Clear indication that a planar graph 'can be drawn' – allow even if candidate implies arcs can cross each other |
| ...no arc meets another arc except at a vertex | B1 | Technical language must be correct (cao) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| e.g. ABCDEGFA | B1 | Any correct Hamiltonian cycle; must start and finish at A; must contain 8 vertices with every vertex appearing only once (except A) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Creates two lists of arcs | M1 | Creates two lists of arcs (with at least three arcs in each list) which contain no common arcs |
| e.g. BG \ | AD; CG \ | BD; EG \ |
| Since no arc appears in both lists, the graph is planar (or draws a planar version) | A1 | cao |
| A1 | Correct reasoning that no arc appears in both lists + so the graph is therefore planar |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| A planar graph is a graph that can be drawn so that... | B1 | Clear indication that a planar graph 'can be drawn' – allow even if candidate implies arcs can cross each other |
| ...no arc meets another arc except at a vertex | B1 | Technical language must be correct (cao) |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. ABCDEGFA | B1 | Any correct Hamiltonian cycle; must start and finish at A; must contain 8 vertices with every vertex appearing only once (except A) |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Creates two lists of arcs | M1 | Creates two lists of arcs (with at least three arcs in each list) which contain no common arcs |
| e.g. BG \| AD; CG \| BD; EG \| AE; CE \| AF | M1 | Four arcs in each list and within each list there are no crossing arcs (cao) |
| Since no arc appears in both lists, the graph is planar (or draws a planar version) | A1 | cao |
| | A1 | Correct reasoning that no arc appears in both lists + so the graph is therefore planar |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_570_663_175_701}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Define what is meant by a planar graph.
\item Starting at A, find a Hamiltonian cycle for the graph in Figure 1.
Arc AG is added to Figure 1 to create the graph shown in Figure 2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_568_666_1226_701}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Taking ABCDEFGA as the Hamiltonian cycle,
\item use the planarity algorithm to determine whether the graph shown in Figure 2 is planar. You must make your working clear and justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 Q2 [7]}}