| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST bounds or theoretical limits |
| Difficulty | Challenging +1.2 This question requires understanding MST properties and graph construction rather than just algorithm application. Part (a) is straightforward (sum 4 smallest edges), but parts (b) and (c) demand insight into which edge configurations are possible for a 5-vertex graph and constructing a valid example—going beyond routine Kruskal's/Prim's algorithm application typical at this level. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
6 A connected graph $G$ has five vertices and has eight edges with lengths $8,10,10,11,13,17$, 17 and 18.
\begin{enumerate}[label=(\alph*)]
\item Find the minimum length of a minimum spanning tree for $G$.
\item Find the maximum length of a minimum spanning tree for $G$.
\item Draw a sketch to show a possible graph $G$ when the length of the minimum spanning tree is 53 .
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q6 [7]}}