| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2018 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Linear Programming |
| Type | Graphical optimization with objective line |
| Difficulty | Standard +0.8 This is a multi-part question combining linear programming with graph theory (degree sequences and Eulerian paths). Part (a) is routine graphical LP (~0.0 difficulty), but parts (b) and (c) require understanding the handshaking lemma, degree sequence constraints, and semi-Eulerian properties to construct a specific graph. The synthesis of LP constraints with graph-theoretic properties and the construction task elevate this above standard Further Maths questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability7.06d Graphical solution: feasible region, two variables |
| Answer | Marks | Guidance |
|---|---|---|
| Draws \(y = x\) | M1 (AO1.1a) | — |
| Correctly labels (or shows by shading) the correct feasible region | A1 (AO1.1b) | — |
| Answer | Marks | Guidance |
|---|---|---|
| Calculates the correct value of \(5x + 4y\) at \((5, 6)\) or \((5.5, 5.5)\) | M1 (AO1.1a) | Value at \((5, 6) = 49\); Value at \((5.5, 5.5) = 49.5\) |
| Finds the correct maximum value of \(5x + 4y\) | A1 (AO1.1b) | Maximum value is \(49.5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Explains the implication of the graph being connected; must refer explicitly to 'connected' | B1 (AO1.2) | The graph is connected, so no vertex can have degree \(0\) |
| Answer | Marks | Guidance |
|---|---|---|
| Explains the implication of the graph being simple; must refer explicitly to 'simple' | B1 (AO1.2) | The graph is simple, so each vertex can only connect at most once to each of the 6 other vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Explains why \(x\) and \(y\) cannot both be 6 | E1 (AO2.4) | If \(x\) and \(y\) are both \(6\) then there would be two vertices that are both adjacent to the other five vertices |
| Completes rigorous argument for \(x + y \leq 11\) | R1 (AO2.1) | However, this would mean that there would be no vertex of degree \(1\) so one of \(x\) or \(y\) has to be at most \(5\). Hence \(x + y \leq 5 + 6\) |
| Answer | Marks | Guidance |
|---|---|---|
| Identifies the need for integer solutions | B1 (AO3.5b) | \(x\) and \(y\) must both be integers |
| Answer | Marks | Guidance |
|---|---|---|
| Uses degree sum \(= 2 \times 8\) to deduce \(x + y\) | M1 (AO2.2a) | \(1+2+3+v+w+x+y = 2 \times 8\); \(16-(1+2+3+4) = x+y\); \(x+y=6\) |
| Infers there are multiple solutions and finds two correct feasible pairs of \(x\) and \(y\) values | M1 (AO2.2b) | \(x=1,\ y=5\); \(x=2,\ y=4\); \(x=3,\ y=3\) |
| Finds all three pairs and no others; condone pairs written as coordinates | A1 (AO1.1b) | — |
| Answer | Marks | Guidance |
|---|---|---|
| Starts to show configuration of \(G\) by drawing a connected graph with exactly 8 edges, OR by listing/labelling the vertex degrees: \(1, 2, 2, 2, 2, 3, 4\) | M1 (AO3.1a) | — |
| Draws a correct graph with degrees: \(1, 2, 2, 2, 2, 3, 4\); NB multiple correct solutions, check by counting degrees | A1 (AO3.2a) | — |
## Question 7(a)(i):
Draws $y = x$ | M1 (AO1.1a) | —
Correctly labels (or shows by shading) the correct feasible region | A1 (AO1.1b) | —
---
## Question 7(a)(ii):
Calculates the correct value of $5x + 4y$ at $(5, 6)$ or $(5.5, 5.5)$ | M1 (AO1.1a) | Value at $(5, 6) = 49$; Value at $(5.5, 5.5) = 49.5$
Finds the correct maximum value of $5x + 4y$ | A1 (AO1.1b) | Maximum value is $49.5$
---
## Question 7(b)(i):
Explains the implication of the graph being connected; must refer explicitly to 'connected' | B1 (AO1.2) | The graph is connected, so no vertex can have degree $0$
---
## Question 7(b)(ii):
Explains the implication of the graph being simple; must refer explicitly to 'simple' | B1 (AO1.2) | The graph is simple, so each vertex can only connect at most once to each of the 6 other vertices
---
## Question 7(b)(iii):
Explains why $x$ and $y$ cannot both be 6 | E1 (AO2.4) | If $x$ and $y$ are both $6$ then there would be two vertices that are both adjacent to the other five vertices
Completes rigorous argument for $x + y \leq 11$ | R1 (AO2.1) | However, this would mean that there would be no vertex of degree $1$ so one of $x$ or $y$ has to be at most $5$. Hence $x + y \leq 5 + 6$
---
## Question 7(b)(iv):
Identifies the need for integer solutions | B1 (AO3.5b) | $x$ and $y$ must both be integers
---
## Question 7(c)(i):
Uses degree sum $= 2 \times 8$ to deduce $x + y$ | M1 (AO2.2a) | $1+2+3+v+w+x+y = 2 \times 8$; $16-(1+2+3+4) = x+y$; $x+y=6$
Infers there are multiple solutions and finds two correct feasible pairs of $x$ and $y$ values | M1 (AO2.2b) | $x=1,\ y=5$; $x=2,\ y=4$; $x=3,\ y=3$
Finds all three pairs and no others; condone pairs written as coordinates | A1 (AO1.1b) | —
---
## Question 7(c)(ii):
Starts to show configuration of $G$ by drawing a connected graph with exactly 8 edges, OR by listing/labelling the vertex degrees: $1, 2, 2, 2, 2, 3, 4$ | M1 (AO3.1a) | —
Draws a correct graph with degrees: $1, 2, 2, 2, 2, 3, 4$; NB multiple correct solutions, check by counting degrees | A1 (AO3.2a) | —7
\begin{enumerate}[label=(\alph*)]
\item (i) Complete Figure 4 to identify the feasible region for the problem.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{5a826f8b-4751-4589-ad0a-109fc5c821f2-12_922_940_849_552}
\end{center}
\end{figure}
7 (a) (ii) Determine the maximum value of $5 x + 4 y$ subject to the constraints.\\
7
\item The simple-connected graph $G$ has seven vertices.
The vertices of $G$ have degree $1,2,3 , v , w , x$ and $y$\\
7 (b) (i) Explain why $x \geq 1$ and $y \geq 1$\\
7 (b) (ii) Explain why $x \leq 6$ and $y \leq 6$\\
7 (b) (iii) Explain why $x + y \leq 11$\\
7 (b) (iv) State an additional constraint that applies to the values of $x$ and $y$ in this context.\\
7
\item The graph $G$ also has eight edges. The inequalities used in part (a)(i) apply to the graph $G$.
7 (c) (i) Given that $v + w = 4$, find all the feasible values of $x$ and $y$.\\
7 (c) (ii) It is also given that the graph $G$ is semi-Eulerian.
On Figure 5, draw $G$.
Figure 5
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2018 Q7 [14]}}