| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2021 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Adjacency matrix interpretation |
| Difficulty | Moderate -0.8 This is a straightforward Further Maths discrete question testing basic graph theory definitions. Part (a) requires identifying zeros in the adjacency matrix (routine observation), part (b) involves checking vertex degrees for Eulerian properties (standard algorithm), and part (c) requires drawing the complement graph (mechanical process of inverting edges). All parts are definitional recall with minimal problem-solving, making this easier than average even for Further Maths content. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| 5(a) | Identifies a missing edge in the | |
| adjacency matrix | 1.1a | M1 |
| Answer | Marks | Guidance |
|---|---|---|
| Explains why G is not complete | 2.4 | A1 |
| Total | 2 | |
| Q | Marking instructions | AO |
| Answer | Marks |
|---|---|
| 5(b) | Explains correctly that G is not |
| Answer | Marks | Guidance |
|---|---|---|
| vertices of odd degree | 2.4 | M1 |
| Answer | Marks | Guidance |
|---|---|---|
| Eulerian | 2.2a | A1 |
| Total | 2 | |
| Q | Marking instructions | AO |
| Answer | Marks |
|---|---|
| 5(c) | Draws a graph with 5 vertices |
| Answer | Marks | Guidance |
|---|---|---|
| and E | 1.1a | M1 |
| Answer | Marks | Guidance |
|---|---|---|
| degrees of 2, 2, 2, 3 and 3 | 1.1a | M1 |
| Draws a fully correct graph | 1.1b | A1 |
| Total | 3 | |
| Question total | 7 | |
| Q | Marking instructions | AO |
Question 5:
--- 5(a) ---
5(a) | Identifies a missing edge in the
adjacency matrix | 1.1a | M1 | There is no edge AD, meaning that
each vertex is not adjacent to every
other vertex so G is not complete.
Explains why G is not complete | 2.4 | A1
Total | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 5(b) ---
5(b) | Explains correctly that G is not
Eulerian by noting that G is not
connected or G contains two
vertices of odd degree | 2.4 | M1 | D and E are only connected to
each other, meaning that G is not
connected. Hence G is neither
Eulerian nor semi-Eulerian.
Deduces correctly that G is
neither Eulerian nor semi-
Eulerian | 2.2a | A1
Total | 2
Q | Marking instructions | AO | Marks | Typical solution
--- 5(c) ---
5(c) | Draws a graph with 5 vertices
which are labelled A, B, C, D
and E | 1.1a | M1
Draws a simple-connected
graph with 5 vertices with
degrees of 2, 2, 2, 3 and 3 | 1.1a | M1
Draws a fully correct graph | 1.1b | A1
Total | 3
Question total | 7
Q | Marking instructions | AO | Marks | Typical solutionAn adjacency matrix for the simple graph $G$ is shown below.
\includegraphics{figure_5}
\begin{enumerate}[label=(\alph*)]
\item Using the adjacency matrix, explain why $G$ is not a complete graph.
[2 marks]
\item State, with a reason, whether $G$ is Eulerian, semi-Eulerian or neither.
[2 marks]
\item Draw a graph that is the complement of $G$
[3 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2021 Q5 [7]}}