| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Moderate -0.8 This D1 question tests basic graph theory definitions and standard algorithms. Part (a) requires stating simple properties of complete graphs (recall only). Part (b) applies the standard formula (n-1)!/2 for Hamiltonian cycles—a direct textbook result requiring minimal problem-solving. Part (c) is a routine quick sort algorithm application with clear steps. All parts are procedural with no novel insight required, making this easier than average A-level maths questions. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02h Hamiltonian paths: and cycles7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | each node is joined to each other node by exactly one arc; no node is joined to itself by a loop | B1 |
| (b) (i) | \(ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA = 6\) (3 choices for 2nd node, 2 for 3rd, 1 for 4th ... \(3 \times 2 \times 1\)) | M1 A1 |
| (b) (ii) | \(4 \times 3 \times 2 \times 1 = 24\) | M1 A1 |
| (b) (iii) | \(9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 362880\) | M1 A1 |
| (c) | Showing sorting stages: \(L_1\) to \(L_7\) with pivot 19 in first list, then 32, 29, 26, 27 in successive stages, ending with complete sort: 17 19 24 25 26 27 29 32 | M2 A2 |
**(a)** | each node is joined to each other node by exactly one arc; no node is joined to itself by a loop | B1 | |
**(b) (i)** | $ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA = 6$ (3 choices for 2nd node, 2 for 3rd, 1 for 4th ... $3 \times 2 \times 1$) | M1 A1 | |
**(b) (ii)** | $4 \times 3 \times 2 \times 1 = 24$ | M1 A1 | |
**(b) (iii)** | $9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 362880$ | M1 A1 | |
**(c)** | Showing sorting stages: $L_1$ to $L_7$ with pivot 19 in first list, then 32, 29, 26, 27 in successive stages, ending with complete sort: 17 19 24 25 26 27 29 32 | M2 A2 | (11) |4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{acc09687-11a3-4392-af17-3d4d331d5ab4-05_501_493_196_529}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 shows the graph $K _ { 4 }$.
\begin{enumerate}[label=(\alph*)]
\item State the features of the graph that identify it as $K _ { 4 }$.
\item In $K _ { 4 }$, the Hamiltonian cycles $A B C D A , B C D A B , C D A B C$ and $D A B C D$ are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
\begin{enumerate}[label=(\roman*)]
\item $\quad K _ { 4 }$,
\item $K _ { 5 }$,
\item $K _ { 10 }$.
\end{enumerate}\item In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres:
$$\begin{array} { l l l l l l l l }
27 & 25 & 29 & 32 & 19 & 24 & 17 & 26
\end{array}$$
Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4 [11]}}