| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Finding variable values in degree sequences |
| Difficulty | Standard +0.3 This is a straightforward application of the handshaking lemma and basic graph theory principles. Part (a) requires simple algebraic manipulation using the given fact about odd-degree vertices, while part (b) involves elementary counting arguments. The question is structured with clear hints and requires only standard textbook techniques with no novel insight or complex problem-solving. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected |
| Answer | Marks | Guidance |
|---|---|---|
| Sum of degrees \(= x + (x+1) + (x+1) + (x+2) + (x+3) = 5x + 7\) | Must be even, \(5x+7\) even \(\Rightarrow 5x\) odd \(\Rightarrow x\) odd | B1, B1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(x\) must satisfy degrees \(\leq 4\) (max degree in simple graph on 5 vertices), so \(x+3 \leq 4 \Rightarrow x \leq 1\); with \(x\) odd and \(x \geq 0\), gives \(x=1\) | B1 | Degrees: \(1,2,2,3,4\) |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum degree \(= 0\), Maximum degree \(= 9\) | B1, B1 | [2 marks] |
| Answer | Marks | Guidance |
|---|---|---|
| If all degrees different, they would be \(0,1,2,...,9\); but degree \(0\) and degree \(9\) cannot coexist in a simple graph (contradiction) | M1, A1 | [2 marks] |
## Question 8:
**Part (a)(i):**
Sum of degrees $= x + (x+1) + (x+1) + (x+2) + (x+3) = 5x + 7$ | Must be even, $5x+7$ even $\Rightarrow 5x$ odd $\Rightarrow x$ odd | B1, B1 | [2 marks]
**Part (a)(ii):**
$x$ must satisfy degrees $\leq 4$ (max degree in simple graph on 5 vertices), so $x+3 \leq 4 \Rightarrow x \leq 1$; with $x$ odd and $x \geq 0$, gives $x=1$ | B1 | Degrees: $1,2,2,3,4$ | Draw valid graph | M1, A1 | [3 marks]
**Part (b)(i):**
Minimum degree $= 0$, Maximum degree $= 9$ | B1, B1 | [2 marks]
**Part (b)(ii):**
If all degrees different, they would be $0,1,2,...,9$; but degree $0$ and degree $9$ cannot coexist in a simple graph (contradiction) | M1, A1 | [2 marks]
---
*Note: Mark allocations above are reconstructed from the question; the actual mark scheme document would be needed for precise guidance notes.*8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.
\begin{enumerate}[label=(\alph*)]
\item A simple graph has five vertices and their degrees are
$$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
\begin{enumerate}[label=(\roman*)]
\item Show that $x$ must be odd.
\item Find the value of $x$ and draw a graph with vertices having the given degrees.
\end{enumerate}\item A simple graph has 10 vertices.
\begin{enumerate}[label=(\roman*)]
\item State the minimum possible degree and maximum possible degree of a vertex.
\item Show that the degrees of the vertices cannot all be different.\\
□\\
□
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q8 [9]}}