| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Easy -1.2 This is a straightforward recall question testing basic graph theory definitions. Part (a) requires simple formula application (n(n-1)/2 for complete graphs) and stating standard properties (MST has n-1 edges, Hamiltonian cycle has n edges). Part (b) requires drawing any Eulerian graph meeting the constraints, which only needs understanding that all vertices must have even degree—a routine exercise with multiple valid solutions. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02d Complete graphs: K_n and number of arcs7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
\begin{enumerate}[label=(\alph*)]
\item The complete graph $K_n$ has every one of its $n$ vertices connected to each of the other vertices by a single edge.
\begin{enumerate}[label=(\roman*)]
\item Find the total number of edges in the graph $K_5$. [1]
\item State the number of edges in a minimum spanning tree for the graph $K_5$. [1]
\item State the number of edges in a Hamiltonian cycle for the graph $K_5$. [1]
\end{enumerate}
\item A simple graph $G$ has six vertices and nine edges, and $G$ is Eulerian. Draw a sketch to show a possible graph $G$. [2]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q6 [5]}}