| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This question tests basic graph theory definitions and properties through recall and simple application. Part (a) and (b) require knowing that a simple connected graph with v vertices needs at least v-1 edges (tree) and at most v(v-1)/2 edges (complete graph), yielding straightforward counting. Part (c) requires recalling that Eulerian means all vertices have even degree and constructing a simple example with 5 vertices that satisfies this but cannot form a Hamiltonian cycle. While it requires understanding multiple concepts, the execution is mechanical with no problem-solving or proof required. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(m = 2, 3, 4, 5\) | B1 | At least 3 correct values stated |
| B1 | All four correct values and no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n = 3, 4, 5, 6\) | B1 | At least 3 correct values |
| B1 | All four correct and no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A valid graph with 5 vertices, all even degree, but no Hamiltonian cycle (e.g. one vertex of degree 4 connected to all others, or a graph where one vertex has degree 2 connecting same pair) | B2 | B2 for correct graph; B1 for graph that is Eulerian but Hamiltonian condition not clearly excluded |
# Question 7:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $m = 2, 3, 4, 5$ | B1 | At least 3 correct values stated |
| | B1 | All four correct values and no extras |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n = 3, 4, 5, 6$ | B1 | At least 3 correct values |
| | B1 | All four correct and no extras |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A valid graph with 5 vertices, all even degree, but no Hamiltonian cycle (e.g. one vertex of degree 4 connected to all others, or a graph where one vertex has degree 2 connecting same pair) | B2 | B2 for correct graph; B1 for graph that is Eulerian but Hamiltonian condition not clearly excluded |7
\begin{enumerate}[label=(\alph*)]
\item A simple connected graph has 4 edges and $m$ vertices. State the possible values of $m$.
\item A simple connected graph has $n$ edges and 4 vertices. State the possible values of $n$.
\item A simple connected graph, $G$, has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph $G$.\\[0pt]
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q7 [6]}}