| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Adding edges to achieve properties |
| Difficulty | Standard +0.3 This is a standard D1 graph theory question testing basic definitions (connected, Hamiltonian, Eulerian) and their application. Part (a) requires recognizing graph components and applying simple rules (odd vertices for Eulerian), while part (b) involves straightforward recall that complete graphs are Eulerian when n is odd, then solving n(n-1)/2 = n. All parts are routine textbook exercises with no novel problem-solving required, making it slightly easier than average. |
| 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 |
|---|---|---|
| \(2\) with 3 triangles diagram | B1, B1 | OE (2 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(3\) with 3 triangles diagram | B1, B1 | OE (2 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(3\) with 4 triangles diagram (dashed line for hidden) | B1, B1 | OE; SC 4: OE diagram shown; B1(must have number and diagram) (2 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(n\) is odd | B1 | (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(3\) (only) | B1 | (1 mark total) |
**8(a)(i)**
| $2$ with 3 triangles diagram | B1, B1 | OE (2 marks total) |
**8(a)(ii)**
| $3$ with 3 triangles diagram | B1, B1 | OE (2 marks total) |
**8(a)(iii)**
| $3$ with 4 triangles diagram (dashed line for hidden) | B1, B1 | OE; SC 4: OE diagram shown; B1(must have number and diagram) (2 marks total) |
**8(b)(i)**
| $n$ is odd | B1 | (1 mark total) |
**8(b)(ii)**
| $3$ (only) | B1 | (1 mark total) |8
\begin{enumerate}[label=(\alph*)]
\item The diagram shows a graph $\mathbf { G }$ with 9 vertices and 9 edges.\\
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708}\\
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105}\\
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
\begin{enumerate}[label=(\roman*)]
\item State the minimum number of edges that need to be added to $\mathbf { G }$ to make a connected graph. Draw an example of such a graph.
\item State the minimum number of edges that need to be added to $\mathbf { G }$ to make the graph Hamiltonian. Draw an example of such a graph.
\item State the minimum number of edges that need to be added to $\mathbf { G }$ to make the graph Eulerian. Draw an example of such a graph.
\end{enumerate}\item A complete graph has $n$ vertices and is Eulerian.
\begin{enumerate}[label=(\roman*)]
\item State the condition that $n$ must satisfy.
\item In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of $n$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q8 [8]}}