| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Ore's theorem application |
| Difficulty | Standard +0.3 This is a straightforward application of standard graph theory results from the Further Maths syllabus. Part (a) requires reading an adjacency matrix (routine skill), part (b) is direct application of Euler's formula V-E+F=2 after counting edges, and part (c) involves systematically checking Ore's theorem condition for non-adjacent pairs. While it requires careful verification, no novel insight or problem-solving is needed—just methodical application of given theorems. Slightly easier than average A-level due to its procedural nature. |
| Spec | 7.02i Ore's theorem: sufficient condition for Hamiltonian graphs7.02m Euler's formula: V + R = E + 27.02q Adjacency matrix: and weighted matrix representation |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) |
| \(A\) | 0 | 1 | 1 | 0 | 1 |
| \(B\) | 1 | 0 | 1 | 0 | 1 |
| \(C\) | 1 | 1 | 0 | 1 | 1 |
| \(D\) | 0 | 0 | 1 | 0 | 1 |
| \(E\) | 1 | 1 | 1 | 1 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Draws a correct labelled graph with edges and vertices (graph P with vertices A, B, C, D, E) | B1 | Correct labelled graph required |
| Answer | Marks | Guidance |
|---|---|---|
| \(v - e + f = 2\) | M1 | Euler's formula correctly recalled |
| 5 vertices \(\Rightarrow v = 5\), 8 edges \(\Rightarrow e = 8\); \(f = 2 + e - v = 2 + 8 - 5 = 5\), therefore graph \(P\) has exactly 5 faces | A1 | Must identify 5 vertices and 8 edges and use Euler's formula |
| Answer | Marks | Guidance |
|---|---|---|
| Vertices \(A\) & \(D\) are not adjacent; vertices \(B\) & \(D\) are not adjacent | M1 | Both pairs must be identified (PI) |
| degree of \(A = 3\), degree of \(B = 3\), degree of \(D = 2\); \(A\) & \(D\): \(3 + 2 = 5\); \(B\) & \(D\): \(3 + 2 = 5\) | A1 | Correct degrees used; condone calculations for \(A\) & \(B\) |
| For each pair of vertices \(X\) and \(Y\) of \(P\) which are not adjacent, degree of \(X\) + degree of \(Y \geq 5\); as \(P\) has 5 vertices, by Ore's theorem, the graph \(P\) is Hamiltonian | R1 | Rigorous argument required concluding both non-adjacent pairs satisfy Ore's condition |
## Question 4:
### Part (a):
| Draws a correct labelled graph with edges and vertices (graph P with vertices A, B, C, D, E) | B1 | Correct labelled graph required |
### Part (b):
| $v - e + f = 2$ | M1 | Euler's formula correctly recalled |
| 5 vertices $\Rightarrow v = 5$, 8 edges $\Rightarrow e = 8$; $f = 2 + e - v = 2 + 8 - 5 = 5$, therefore graph $P$ has exactly 5 faces | A1 | Must identify 5 vertices and 8 edges and use Euler's formula |
### Part (c):
| Vertices $A$ & $D$ are not adjacent; vertices $B$ & $D$ are not adjacent | M1 | Both pairs must be identified (PI) |
| degree of $A = 3$, degree of $B = 3$, degree of $D = 2$; $A$ & $D$: $3 + 2 = 5$; $B$ & $D$: $3 + 2 = 5$ | A1 | Correct degrees used; condone calculations for $A$ & $B$ |
| For each pair of vertices $X$ and $Y$ of $P$ which are not adjacent, degree of $X$ + degree of $Y \geq 5$; as $P$ has 5 vertices, by Ore's theorem, the graph $P$ is Hamiltonian | R1 | Rigorous argument required concluding both non-adjacent pairs satisfy Ore's condition |
---4 The connected planar graph $P$ has the adjacency matrix
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$A$ & 0 & 1 & 1 & 0 & 1 \\
\hline
$B$ & 1 & 0 & 1 & 0 & 1 \\
\hline
$C$ & 1 & 1 & 0 & 1 & 1 \\
\hline
$D$ & 0 & 0 & 1 & 0 & 1 \\
\hline
$E$ & 1 & 1 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
4
\begin{enumerate}[label=(\alph*)]
\item Draw $P$
4
\item Using Euler's formula for connected planar graphs, show that $P$ has exactly 5 faces.
4
\item Ore's theorem states that a simple graph with $n$ vertices is Hamiltonian if, for every pair of vertices $X$ and $Y$ which are not adjacent,
$$\text { degree of } X + \text { degree of } Y \geq n$$
where $n \geq 3$\\
Using Ore's theorem, prove that the graph $P$ is Hamiltonian.\\
Fully justify your answer.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2019 Q4 [6]}}