| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Impossibility proofs for degree sequences |
| Difficulty | Moderate -0.3 This is a multi-part D1 question covering standard graph theory topics (handshaking lemma, Eulerian trails, Prim's algorithm, TSP bounds). Part (i) is straightforward application of the handshaking lemma, parts (ii)-(iii) are routine algorithmic procedures, and part (iv) requires standard MST-based bounds. While lengthy, all components are textbook exercises requiring recall and careful execution rather than novel problem-solving, making it slightly easier than average. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | |
| \(A\) | - | 5 | 3 | 8 | 2 |
| \(B\) | 5 | - | 6 | - | - |
| \(C\) | 3 | 6 | - | 7 | - |
| \(D\) | 8 | - | 7 | - | 9 |
| \(E\) | 2 | - | - | 9 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(5 \times 3 = 15\) which is odd, so sum of degrees would be odd, which is impossible | B1 | Must mention odd sum of degrees or handshaking lemma |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Exactly two odd vertices (\(B\) order 3, \(D\) order 3); \(A\), \(C\), \(E\) are even | M1 | |
| Semi-Eulerian trail stated e.g. \(B \to A \to C \to D \to E \to A \to \ldots \to D\) | A1 | Must start and end at odd vertices \(B\) and \(D\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Start at \(A\); select \(AE=2\) | M1 | Correct application of Prim's |
| Select \(AC=3\) | A1 | |
| Select \(AB=5\) or \(BC=6\) chosen correctly | A1 | Minimum spanning tree with total weight = \(2+3+5+7=17\) or similar; tree drawn correctly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Lower bound: remove \(A\), find MST of remainder + two least arcs from \(A\) | M1 | |
| Lower bound value stated correctly | A1 | |
| Nearest neighbour from \(A\): \(A \to E(2) \to \ldots\) tour stated | M1 | |
| Upper bound total calculated | A1 | |
| Nearest neighbour fails from \(F\) because \(F\) is only connected to \(C\) and \(D\), so after visiting both, cannot reach remaining vertices without revisiting | B1 |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $5 \times 3 = 15$ which is odd, so sum of degrees would be odd, which is impossible | B1 | Must mention odd sum of degrees or handshaking lemma |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Exactly two odd vertices ($B$ order 3, $D$ order 3); $A$, $C$, $E$ are even | M1 | |
| Semi-Eulerian trail stated e.g. $B \to A \to C \to D \to E \to A \to \ldots \to D$ | A1 | Must start and end at odd vertices $B$ and $D$ |
## Part (iii) – Prim's algorithm
| Answer | Marks | Guidance |
|--------|-------|----------|
| Start at $A$; select $AE=2$ | M1 | Correct application of Prim's |
| Select $AC=3$ | A1 | |
| Select $AB=5$ or $BC=6$ chosen correctly | A1 | Minimum spanning tree with total weight = $2+3+5+7=17$ or similar; tree drawn correctly |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Lower bound: remove $A$, find MST of remainder + two least arcs from $A$ | M1 | |
| Lower bound value stated correctly | A1 | |
| Nearest neighbour from $A$: $A \to E(2) \to \ldots$ tour stated | M1 | |
| Upper bound total calculated | A1 | |
| Nearest neighbour fails from $F$ because $F$ is only connected to $C$ and $D$, so after visiting both, cannot reach remaining vertices without revisiting | B1 | |
---2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.
A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.\\
A simply connected graph is one that is both simple and connected.\\
(i) Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.\\
(ii) A simply connected graph has five vertices $A , B , C , D$ and $E$, in which $A$ has order $4 , B$ has order 2, $C$ has order 3, $D$ has order 3 and $E$ has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph.
A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.
\begin{center}
\begin{tabular}{ c | c | c | c | c | c }
& $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$A$ & - & 5 & 3 & 8 & 2 \\
\hline
$B$ & 5 & - & 6 & - & - \\
\hline
$C$ & 3 & 6 & - & 7 & - \\
\hline
$D$ & 8 & - & 7 & - & 9 \\
\hline
$E$ & 2 & - & - & 9 & - \\
\hline
\end{tabular}
\end{center}
(iii) Apply Prim's algorithm to the network, showing all your working, starting at vertex $A$. Draw the resulting tree and state its total weight.
A sixth vertex, $F$, is added to the network using arcs $C F$ and $D F$, each of which has weight 6 .\\
(iv) Use your answer to part (iii) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex $A$, to find an upper bound for the length of this tour. Explain why the nearest neighbour method fails if it is started from vertex $F$.
\hfill \mbox{\textit{OCR D1 2010 Q2 [10]}}