| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Kuratowski's theorem |
| Difficulty | Challenging +1.8 Part (a) requires applying Euler's formula (V - E + F = 2) to solve a system with algebraic expressions, involving quadratic manipulation and constraint checking—moderately challenging algebra in a graph theory context. Part (b) requires knowledge of Kuratowski's theorem or using inequalities for planar graphs (E ≤ 3V - 6) to prove K₆ is non-planar, which is a standard Further Maths result but requires formal justification beyond simple recall. |
| Spec | 7.02l Planar graphs: planarity, subdivision, contraction7.02m Euler's formula: V + R = E + 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Uses Euler's formula: \((x+1)^2 - (25+2x-2y) + (y-1)^2 = 2\) | M1 (AO3.1a) | Uses Euler's formula for connected planar graphs |
| \(x^2 + 2x + 1 - 25 - 2x + 2y + y^2 - 2y + 1 = 2\) | A1 (AO1.1b) | Finds correct equation in terms of \(x\) and \(y\) |
| \(x^2 + y^2 = 25\) | M1 (AO1.1a) | Expands and simplifies |
| \(x=3, y=4\) or \(x=4, y=3\) | A1 (AO1.1b) | Two correct pairs of integer values |
| For \(x=3, y=4\): vertices \(=16\), edges \(=23\), faces \(=9\) | A1 (AO3.2a) | One correct set of values for vertices, edges and faces |
| For \(x=4, y=3\): vertices \(=25\), edges \(=27\), faces \(=4\) | A1 (AO3.2a) | Both correct sets of values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(K_6\) has a subgraph which is \(K_5\); Kuratowski's theorem states that a graph which contains a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\) is not planar | E1 (AO2.4) | Explains \(K_6\) contains a subgraph which is \(K_5\), OR explains \(K_6\) contains a subgraph which is \(K_{3,3}\) |
| Hence \(K_6\) is not planar | R1 (AO2.1) | Completes rigorous proof with reference to Kuratowski's theorem |
## Question 6(a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Uses Euler's formula: $(x+1)^2 - (25+2x-2y) + (y-1)^2 = 2$ | M1 (AO3.1a) | Uses Euler's formula for connected planar graphs |
| $x^2 + 2x + 1 - 25 - 2x + 2y + y^2 - 2y + 1 = 2$ | A1 (AO1.1b) | Finds correct equation in terms of $x$ and $y$ |
| $x^2 + y^2 = 25$ | M1 (AO1.1a) | Expands and simplifies |
| $x=3, y=4$ or $x=4, y=3$ | A1 (AO1.1b) | Two correct pairs of integer values |
| For $x=3, y=4$: vertices $=16$, edges $=23$, faces $=9$ | A1 (AO3.2a) | One correct set of values for vertices, edges and faces |
| For $x=4, y=3$: vertices $=25$, edges $=27$, faces $=4$ | A1 (AO3.2a) | Both correct sets of values |
**Total: 6 marks**
---
## Question 6(b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $K_6$ has a subgraph which is $K_5$; Kuratowski's theorem states that a graph which contains a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ is not planar | E1 (AO2.4) | Explains $K_6$ contains a subgraph which is $K_5$, OR explains $K_6$ contains a subgraph which is $K_{3,3}$ |
| Hence $K_6$ is not planar | R1 (AO2.1) | Completes rigorous proof with reference to Kuratowski's theorem |
**Total: 2 marks**
---6
\begin{enumerate}[label=(\alph*)]
\item A connected planar graph has $( x + 1 ) ^ { 2 }$ vertices, $( 25 + 2 x - 2 y )$ edges and $( y - 1 ) ^ { 2 }$ faces, where $x > 0$ and $y > 0$
Find the possible values for the number of vertices, edges and faces for the graph.\\[0pt]
[6 marks]\\
LL\\
6
\item Explain why $K _ { 6 }$, the complete graph with 6 vertices, is not planar.
Fully justify your answer.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2021 Q6 [8]}}