| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Moderate -0.8 This question tests basic graph theory definitions and properties through straightforward recall and simple application. Part (a) requires knowing a spanning tree has m-1 edges (leading to n ≥ m-1), part (b) asks for the trivial fact that a Hamiltonian cycle has m edges, and part (c) requires drawing any Eulerian graph with specified parameters (all vertices even degree). No problem-solving or novel insight needed—pure definitional knowledge. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
7 A connected graph $\mathbf { G }$ has $m$ vertices and $n$ edges.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Write down the number of edges in a minimum spanning tree of $\mathbf { G }$.
\item Hence write down an inequality relating $m$ and $n$.
\end{enumerate}\item The graph $\mathbf { G }$ contains a Hamiltonian cycle. Write down the number of edges in this cycle.
\item In the case where $\mathbf { G }$ is Eulerian, draw a graph of $\mathbf { G }$ for which $m = 6$ and $n = 12$.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q7 [6]}}