| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Vertex degree sequences |
| Difficulty | Moderate -0.5 This question tests fundamental graph theory concepts (handshaking lemma, Eulerian paths, trees) through straightforward applications. Part (a) is direct recall, parts (b-c) require constructing simple examples with clear constraints, and part (d) needs basic logical reasoning about degree sequences. While it requires understanding multiple concepts, none demand novel insight or complex multi-step reasoning—these are standard D1 exercises testing definitional understanding. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| (a) 14 | B1 | 1 mark total |
| (b) Graph with 5 vertices and 5 edges and exactly one vertex of degree 4 (but may not be simple) | M1 | |
| Simple & semi-Eulerian | A1 | 2 marks total |
| (c) Graph with 5 vertices that is: semi-Eulerian | B1 | |
| a tree | B1 | 2 marks total |
| (d) Graph is simple therefore each vertex of degree 5 must be connected to each of the other 5 vertices. The remaining four vertices must each be connected to the two vertices of degree 5. Therefore no vertex has degree 1. | E1 | Must include 'simple' (or a full definition) or 'no vertex can have degree greater than 5' as a reason within the explanation. |
| E1 | 2 marks total |
**(a)** 14 | B1 | 1 mark total
**(b)** Graph with 5 vertices and 5 edges and exactly one vertex of degree 4 (but may not be simple) | M1 |
Simple & semi-Eulerian | A1 | 2 marks total
**(c)** Graph with 5 vertices that is: semi-Eulerian | B1 |
a tree | B1 | 2 marks total
**(d)** Graph is simple therefore each vertex of degree 5 must be connected to each of the other 5 vertices. The remaining four vertices must each be connected to the two vertices of degree 5. Therefore no vertex has degree 1. | E1 | Must include 'simple' (or a full definition) or 'no vertex can have degree greater than 5' as a reason within the explanation.
| E1 | 2 marks total
**Total: 7 marks**
---6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.
\begin{enumerate}[label=(\alph*)]
\item A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
\item Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
\item Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
\item A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2016 Q6 [7]}}