| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Kuratowski's theorem |
| Difficulty | Standard +0.3 This question tests standard graph theory results from D1 (non-planarity of Kâ and Kâ,â). Parts (a) and (c) are straightforward drawing tasks. Parts (b) and (d) require applying Euler's formula or Kuratowski's theorem, which are bookwork results typically memorized. While it requires understanding of planar graphs, the demonstrations follow well-established methods taught directly in the syllabus with no novel problem-solving required. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks | Guidance |
|---|---|---|
| (a) [Diagram of complete graph \(K_5\)] | B1 | |
| (b) e.g. ABCDEA is a Hamiltonian cycle choose AC inside so BD and BC must go outside put AD or CE inside, then the other cannot be placed without overlapping so no planar drawing is possible | B2 | |
| (c) [Diagram showing bipartite graph \(K_{3,3}\)] | B1 | |
| (d) e.g. AEBFCDA is a Hamiltonian cycle, redraw as polygon: [polygon diagram] choose AD inside so BF and CE must go outside but this creates a crossing outside so no planar drawing is possible | B2 | (6) |
**(a)** [Diagram of complete graph $K_5$] | B1 |
**(b)** e.g. ABCDEA is a Hamiltonian cycle choose AC inside so BD and BC must go outside put AD or CE inside, then the other cannot be placed without overlapping so no planar drawing is possible | B2 |
**(c)** [Diagram showing bipartite graph $K_{3,3}$] | B1 |
**(d)** e.g. AEBFCDA is a Hamiltonian cycle, redraw as polygon: [polygon diagram] choose AD inside so BF and CE must go outside but this creates a crossing outside so no planar drawing is possible | B2 | (6) |
---\begin{enumerate}[label=(\alph*)]
\item Draw the complete graph $K_5$. [1 mark]
\item Demonstrate that no planar drawing is possible for $K_5$. [2 marks]
\item Draw the complete graph $K_{3,3}$. [1 mark]
\item Demonstrate that no planar drawing is possible for $K_{3,3}$. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q1 [6]}}