| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | November |
| Marks | 5 |
| 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 the D1 planarity algorithm following a prescribed Hamiltonian cycle. Students need to draw the graph (routine), then mechanically apply the algorithm by checking whether each remaining edge can be added inside or outside the cycle. While it requires careful bookkeeping across 4 marks, it involves no conceptual insight—just following a learned procedure with a small graph (6 vertices). Slightly easier than average due to its algorithmic nature. |
| Spec | 7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Component | Must be connected to |
| \(A\) | \(B , D , E , F\) |
| \(B\) | \(C , D , E\) |
| \(C\) | \(D , E\) |
| \(D\) | \(E\) |
| \(E\) | \(F\) |
| \(F\) | \(B\) |
2. An electronics company makes a product that consists of components $A , B , C , D , E$ and $F$. The table shows which components must be connected together to make the product work. The components are all placed on a circuit board and connected by wires, which are not allowed to cross.
\begin{center}
\begin{tabular}{ | c | c | }
\hline
Component & Must be connected to \\
\hline
$A$ & $B , D , E , F$ \\
\hline
$B$ & $C , D , E$ \\
\hline
$C$ & $D , E$ \\
\hline
$D$ & $E$ \\
\hline
$E$ & $F$ \\
\hline
$F$ & $B$ \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item On the diagram in the answer book draw straight lines to show which components need to be connected.\\
(1)
\item Starting with the Hamiltonian cycle $A B C D E F A$, use the planarity algorithm to determine whether it is possible to build this product on a circuit board.\\
(4)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q2 [5]}}