| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Moderate -0.8 This is a straightforward recall and application question on basic graph theory definitions. Parts (a) and (b) are routine calculations using the formula for edges in a complete graph, while part (c) requires stating standard results about complete graphs. No problem-solving or novel insight is required—just knowledge of definitions and formulas from the D1 specification. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct \(K_4\) drawn (4 vertices, each connected to every other — 6 edges total) | B1 | Must show all 6 edges clearly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\frac{8 \times 7}{2} = 28\) edges | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Each vertex has degree 7 (odd), so not Eulerian | B1 | Must reference odd degree / not all even |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\frac{n(n-1)}{2}\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n - 1\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n\) is odd | B1 | Each vertex has degree \(n-1\), which is even when \(n\) is odd |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Hamiltonian cycle has \(n\) edges; Eulerian cycle has \(\frac{n(n-1)}{2}\) edges; setting equal: \(n = \frac{n(n-1)}{2}\) giving \(n=3\) | M1 A1 | M1 for equating the two expressions, A1 for \(n=3\) |
## Question 6:
**(a)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct $K_4$ drawn (4 vertices, each connected to every other — 6 edges total) | B1 | Must show all 6 edges clearly |
**(b)(i)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\frac{8 \times 7}{2} = 28$ edges | B1 | |
**(b)(ii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Each vertex has degree 7 (odd), so not Eulerian | B1 | Must reference odd degree / not all even |
**(c)(i)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\frac{n(n-1)}{2}$ | B1 | |
**(c)(ii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n - 1$ | B1 | |
**(c)(iii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n$ is odd | B1 | Each vertex has degree $n-1$, which is even when $n$ is odd |
**(c)(iv)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Hamiltonian cycle has $n$ edges; Eulerian cycle has $\frac{n(n-1)}{2}$ edges; setting equal: $n = \frac{n(n-1)}{2}$ giving $n=3$ | M1 A1 | M1 for equating the two expressions, A1 for $n=3$ |
---6 The complete graph $K _ { n } ( n > 1 )$ has every one of its $n$ vertices connected to each of the other vertices by a single edge.
\begin{enumerate}[label=(\alph*)]
\item Draw the complete graph $K _ { 4 }$.
\item \begin{enumerate}[label=(\roman*)]
\item Find the total number of edges for the graph $K _ { 8 }$.
\item Give a reason why $K _ { 8 }$ is not Eulerian.
\end{enumerate}\item For the graph $K _ { n }$, state in terms of $n$ :
\begin{enumerate}[label=(\roman*)]
\item the total number of edges;
\item the number of edges in a minimum spanning tree;
\item the condition for $K _ { n }$ to be Eulerian;
\item the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q6 [7]}}