| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | State number of edges formula |
| Difficulty | Easy -2.0 Part (a) tests direct recall of the fundamental MST formula (n-1 edges), requiring no problem-solving. Part (b) applies Kruskal's algorithm mechanically to a small network—a standard textbook exercise with no novel insight needed. This is significantly easier than average A-level content. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(9\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n-1\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(GI = 5\) | B1 | 9 edges |
| \(AB = 6\) | M1 | SCA |
| \(EI = 7\) | A1 | start with \(GI\) |
| \(BD = 8\) | ||
| ~~\(EG = 9\)~~ | ||
| \(IJ = 10\) | A1 | \(IJ\) fifth |
| \(HJ = 11\) | ||
| ~~\(HI = 12\)~~ | ||
| \(AF = 13\) | ||
| \(DE = 14\) | ||
| \(CG = 15\) | A1 | all correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(89\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct spanning tree diagram drawn | M1 | 9 edges |
| Fully correct | A1 |
## Question 3:
### Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $9$ | B1 | |
**Total: 1 mark**
### Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n-1$ | B1 | |
**Total: 1 mark**
### Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $GI = 5$ | B1 | 9 edges |
| $AB = 6$ | M1 | SCA |
| $EI = 7$ | A1 | start with $GI$ |
| $BD = 8$ | | |
| ~~$EG = 9$~~ | | |
| $IJ = 10$ | A1 | $IJ$ fifth |
| $HJ = 11$ | | |
| ~~$HI = 12$~~ | | |
| $AF = 13$ | | |
| $DE = 14$ | | |
| $CG = 15$ | A1 | all correct |
**Total: 5 marks**
### Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $89$ | B1 | |
**Total: 1 mark**
### Part (b)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct spanning tree diagram drawn | M1 | 9 edges |
| Fully correct | A1 | |
**Total: 2 marks**
---3
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the number of edges in a minimum spanning tree of a network with 10 vertices.
\item State the number of edges in a minimum spanning tree of a network with $n$ vertices.
\end{enumerate}\item The following network has 10 vertices: $A , B , \ldots , J$. The numbers on each edge represent the distances, in miles, between pairs of vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
\begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm to find the minimum spanning tree for the network.
\item State the length of your spanning tree.
\item Draw your spanning tree.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q3 [15]}}