| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This question tests basic graph theory definitions and formulas (minimum edges = n-1 for connected graphs, maximum = n(n-1)/2 for simple graphs, handshaking lemma). All parts require direct recall or simple substitution into standard formulas with no problem-solving or novel insight needed. While multi-part, each component is straightforward bookwork typical of D1 module. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Minimum edges \(= 7\) | B1 | For a connected graph on 8 vertices |
| (ii) Maximum edges \(= 28\) | B1 | \(\frac{8 \times 7}{2} = 28\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Minimum edges \(= n - 1\) | B1 | |
| (ii) Maximum edges \(= \frac{n(n-1)}{2}\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Possible values of \(d\): \(0, 1, 2, 3, 4, 5\) | B1 | All values \(0 \leq d \leq 5\) |
| (ii) If connected: \(d = 1, 2, 3, 4, 5\) | B1 | Excludes \(d = 0\) |
| (iii) If Eulerian: \(d = 2, 4\) | B2 | Must be even and connected; B1 for one correct value |
# Question 7:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) Minimum edges $= 7$ | B1 | For a connected graph on 8 vertices |
| (ii) Maximum edges $= 28$ | B1 | $\frac{8 \times 7}{2} = 28$ |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) Minimum edges $= n - 1$ | B1 | |
| (ii) Maximum edges $= \frac{n(n-1)}{2}$ | B1 | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) Possible values of $d$: $0, 1, 2, 3, 4, 5$ | B1 | All values $0 \leq d \leq 5$ |
| (ii) If connected: $d = 1, 2, 3, 4, 5$ | B1 | Excludes $d = 0$ |
| (iii) If Eulerian: $d = 2, 4$ | B2 | Must be even and connected; B1 for one correct value |7
\begin{enumerate}[label=(\alph*)]
\item A simple connected graph $X$ has eight vertices.
\begin{enumerate}[label=(\roman*)]
\item State the minimum number of edges of the graph.
\item Find the maximum number of edges of the graph.
\end{enumerate}\item A simple connected graph $Y$ has $n$ vertices.
\begin{enumerate}[label=(\roman*)]
\item State the minimum number of edges of the graph.
\item Find the maximum number of edges of the graph.
\end{enumerate}\item A simple graph $Z$ has six vertices and each of the vertices has the same degree $d$.
\begin{enumerate}[label=(\roman*)]
\item State the possible values of $d$.
\item If $Z$ is connected, state the possible values of $d$.
\item If $Z$ is Eulerian, state the possible values of $d$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q7 [8]}}