| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Planarity algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward D1 question testing basic graph theory definitions and standard algorithms. Part (a) requires simple recall of graph terminology, part (b) is routine completion of a Hamiltonian cycle with minimal problem-solving, and part (c) applies a standard planarity algorithm mechanically. The 6-mark total and algorithmic nature make this easier than average A-level questions. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02h Hamiltonian paths: and cycles7.02l Planar graphs: planarity, subdivision, contraction |
| Answer | Marks |
|---|---|
| n bipartite graph | B1 (1) |
| Answer | Marks |
|---|---|
| A, 3, 6, 4, 6, C, 1, D, 2, 7, A | B2, 1, 0 (2) |
| Answer | Marks |
|---|---|
| [Diagram showing Redrawing with 3-D representation] | M1, A1 |
| Identifying that it is not planar | A1 (3), [6] |
## 3(a)
| n bipartite graph | B1 (1) |
## 3(b)
| A, 3, 6, 4, 6, C, 1, D, 2, 7, A | B2, 1, 0 (2) |
## 3(c)
| [Diagram showing Redrawing with 3-D representation] | M1, A1 |
| Identifying that it is not planar | A1 (3), [6] |\includegraphics{figure_3}
\begin{enumerate}[label=(\alph*)]
\item Write down the name given to the type of graph drawn in Figure 3. (1)
\end{enumerate}
A Hamiltonian cycle for the graph in Figure 3 begins A, 3, B, ....
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Complete this Hamiltonian cycle. (2)
\item Starting with the Hamiltonian cycle found in (b), use the planarity algorithm to determine if the graph is planar. (3)
\end{enumerate}
(Total 6 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q3}}