| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Adding edges to achieve properties |
| Difficulty | Moderate -0.3 This D1 question tests standard graph theory definitions (connected, Hamiltonian, Eulerian) with straightforward applications. Part (a) requires adding minimum edges using well-known criteria, and part (b) involves direct recall of conditions for complete graphs. While multi-part, each component is a textbook exercise requiring minimal problem-solving beyond applying memorized definitions. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Add 3 edges to connect the 4 separate squares into one connected graph | B1 | Minimum 3 edges needed |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Add edges to allow a Hamiltonian cycle visiting all 16 vertices | M1 | Must visit all vertices exactly once |
| Correct addition of minimum edges (3 edges) shown | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| All vertices must have even degree for Eulerian graph | M1 | |
| Correct minimum edges added to give all vertices even degree | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n\) must be odd | B1 | For complete graph \(K_n\) to be Eulerian, all vertices must have even degree; each vertex has degree \(n-1\), so \(n-1\) must be even |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Hamiltonian cycle has \(n\) edges; Eulerian trail has \(\frac{n(n-1)}{2}\) edges | M1 | Setting equal: \(n = \frac{n(n-1)}{2}\) |
| \(n = \mathbf{3}\) | A1 | \(2 = n-1 \Rightarrow n = 3\) |
## Question 7:
### Part (a)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Add **3 edges** to connect the 4 separate squares into one connected graph | B1 | Minimum 3 edges needed |
### Part (a)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Add edges to allow a Hamiltonian cycle visiting all 16 vertices | M1 | Must visit all vertices exactly once |
| Correct addition of minimum edges (3 edges) shown | A1 | |
### Part (a)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| All vertices must have even degree for Eulerian graph | M1 | |
| Correct minimum edges added to give all vertices even degree | A1 | |
### Part (b)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n$ must be **odd** | B1 | For complete graph $K_n$ to be Eulerian, all vertices must have even degree; each vertex has degree $n-1$, so $n-1$ must be even |
### Part (b)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Hamiltonian cycle has $n$ edges; Eulerian trail has $\frac{n(n-1)}{2}$ edges | M1 | Setting equal: $n = \frac{n(n-1)}{2}$ |
| $n = \mathbf{3}$ | A1 | $2 = n-1 \Rightarrow n = 3$ |
I can see these pages are from an AQA MD01 Decision Mathematics insert paper (June 2009) containing figures for use with questions — they show a network graph (Figure 1), a blank coordinate grid (Figure 2), and sets of square graphs labeled as Connected, Hamiltonian, and Eulerian (Figures 3-5).
However, these pages are the **insert/question figures only** — they do not contain a mark scheme. There is no mark allocation, working, or examiner guidance on these pages.
To find the mark scheme for AQA MD01 June 2009, you would need to access:
- The **separate mark scheme document** (not shown here)
- Available from AQA's website or revision platforms such as Physics & Maths Tutor (PMT)
Would you like me to help you interpret or work through any of the questions that use these figures instead?7
\begin{enumerate}[label=(\alph*)]
\item The diagram shows a graph with 16 vertices and 16 edges.\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_365_758}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_365_1080}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_689_758}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_200_689_1082}
\begin{enumerate}[label=(\roman*)]
\item On Figure 1 below, add the minimum number of edges to make a connected graph.
\item On Figure 2 opposite, add the minimum number of edges to make the graph Hamiltonian.
\item On Figure 3 opposite, add the minimum number of edges to make the graph Eulerian.
\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 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$.
\section*{Figure 1}
\section*{Connected Graph}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(a)(i)}
\includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_195_200_2014_758}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(a)(i)}
\includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_197_200_2012_1082}
\end{center}
\end{figure}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_758}
\end{center}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(a)(i)}
\includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_1080}
\end{center}
\end{figure}
\section*{Figure 2}
\section*{Hamiltonian Graph}
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_218_536_511_753}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_213_212_836_753}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_215_214_836_1073}\\
(a)(iii)
\section*{Eulerian Graph}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_207_204_1356_758}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_211_206_1354_1078}
\end{center}
\end{figure}
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_206_209_1681_753}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_200_202_1681_1080}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q7 [8]}}