| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2023 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Eulerian classification |
| Difficulty | Moderate -0.3 This question tests fundamental definitions and theorems in graph theory (simple graphs, Eulerian graphs, isomorphism, Euler's formula) with straightforward application. Part (a) requires stating definitions, (b) involves basic degree sequence comparison, and (c) requires identifying that G is non-planar—all standard Further Maths content requiring recall and direct application rather than problem-solving insight. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability7.02i Ore's theorem: sufficient condition for Hamiltonian graphs7.02l Planar graphs: planarity, subdivision, contraction7.02m Euler's formula: V + R = E + 2 |
| Answer | Marks | Guidance |
|---|---|---|
| States that \(G\) does not contain any multiple edges OR states that \(G\) does not contain any loops | M1 | AO 1.1a |
| States that \(G\) does not contain any multiple edges AND does not contain any loops, and then deduces that \(G\) is simple | A1 | AO 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Explains that \(G\) is connected OR explains that \(G\) only has vertices with even degree | M1 | AO 2.4 |
| Completes a reasoned argument with reference to \(G\) satisfying the two conditions necessary for a graph to be Eulerian | R1 | AO 2.1 |
| Answer | Marks | Guidance |
|---|---|---|
| States that the vertices of \(G\) and \(H\) have the same degrees | M1 | AO 1.1a |
| Answer | Marks | Guidance |
|---|---|---|
| Infers that \(H\) may be isomorphic to \(G\). Must not be definite | A1 | AO 2.2b |
| Answer | Marks | Guidance |
|---|---|---|
| Recalls that the formula \(v - e + f = 2\) can only be used with (connected) planar graphs | B1 | AO 1.2 |
| Translates the problem into that of showing \(G\) is non-planar by stating that \(G\) contains a subgraph isomorphic to \(K_{3,3}\) | M1 | AO 3.1a |
| Completes a reasoned argument with reference to Kuratowski's theorem, and concludes that \(G\) is non-planar and so doesn't meet the conditions for the formula | R1 | AO 2.1 |
## Question 8(a)(i):
States that $G$ does not contain any multiple edges OR states that $G$ does not contain any loops | M1 | AO 1.1a
States that $G$ does not contain any multiple edges AND does not contain any loops, and then deduces that $G$ is simple | A1 | AO 2.2a
Typical solution: $G$ has no multiple edges or loops, therefore $G$ is simple.
---
## Question 8(a)(ii):
Explains that $G$ is connected OR explains that $G$ only has vertices with even degree | M1 | AO 2.4
Completes a reasoned argument with reference to $G$ satisfying the two conditions necessary for a graph to be Eulerian | R1 | AO 2.1
Typical solution: $G$ is a connected graph and all of its vertices have an even degree. Therefore $G$ meets the two conditions necessary for a graph to be Eulerian.
---
## Question 8(b):
States that the vertices of $G$ and $H$ have the same degrees | M1 | AO 1.1a
$G$ also has vertices with degrees $2, 4, 4, 4, 4, 4$ and $4$.
Infers that $H$ may be isomorphic to $G$. Must not be definite | A1 | AO 2.2b
However, this does not necessarily mean the two graphs are isomorphic.
---
## Question 8(c):
Recalls that the formula $v - e + f = 2$ can only be used with (connected) planar graphs | B1 | AO 1.2
Translates the problem into that of showing $G$ is non-planar by stating that $G$ contains a subgraph isomorphic to $K_{3,3}$ | M1 | AO 3.1a
Completes a reasoned argument with reference to Kuratowski's theorem, and concludes that $G$ is non-planar and so doesn't meet the conditions for the formula | R1 | AO 2.1
Typical solution: The formula $v - e + f = 2$ can only be used with connected, planar graphs. However, $G$ contains a subgraph isomorphic to complete bipartite graph $K_{3,3}$. Hence, by Kuratowski's theorem, $G$ is non-planar and so the formula $v - e + f = 2$ cannot be used with $G$.
---8 The graph $G$ is shown below.\\
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-12_301_688_351_676}
8
\begin{enumerate}[label=(\alph*)]
\item (i) State, with a reason, whether or not $G$ is simple.
8 (a) (ii) A student states that $G$ is Eulerian.\\
Explain why the student is correct.
8
\item The graph $H$ has 8 vertices with degrees 2, 2, 4, 4, 4, 4, 4 and 4 Comment on whether $H$ is isomorphic to $G$\\
8
\item The formula $v - e + f = 2$, where\\
$v =$ number of vertices\\
$e =$ number of edges\\
$f =$ number of faces\\
can be used with graphs which satisfy certain conditions.
Prove that $G$ does not satisfy the conditions for the above formula to apply.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2023 Q8 [6]}}