| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2022 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Ore's theorem application |
| Difficulty | Challenging +1.2 This is a multi-part Further Maths question covering graph theory concepts (Hamiltonian graphs, Ore's theorem, bipartite graphs, Kuratowski's theorem, thickness). While it requires knowledge of several specialized theorems, most parts involve direct application of definitions and algorithms rather than deep problem-solving. Part (d) requiring a Hamiltonian proof and part (g) on thickness require more insight, but the structured nature and algorithmic parts (a,b,e) make this moderately above average difficulty for Further Maths content. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.02f Bipartite test: colouring argument7.02h Hamiltonian paths: and cycles7.02i Ore's theorem: sufficient condition for Hamiltonian graphs7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions7.02o Thickness: of graphs |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | e.g. A B F C D H E |
| [1] | 1.2 | A valid path through 7 of the vertices (no repeats) |
| 4 | (b) | e.g. A B E H G C A |
| [1] | 1.2 | A valid cycle through 6 of the vertices (no repeats, closed) |
| 4 | (c) | e.g. D and G |
| have degree sum 2 + 2 = 4 which is less than 8 | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 2.4 | Identifying any pair of non-adjacent vertices, not including C or H |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (d) | e.g. |
| Answer | Marks |
|---|---|
| so at least one of C and H must be repeated | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 2.1 | Or equivalent valid explanation of why there cannot be a cycle |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (e) | Output: bipartite |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | A, D, E, F, G = and B, C, H = |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (f) | Graph contains K as a subgraph |
| Answer | Marks |
|---|---|
| Hence graph is non-planar | M1 |
| Answer | Marks |
|---|---|
| [3] | 2.2a |
| Answer | Marks |
|---|---|
| 1.1 | K only (not ‘graph contains K or K ’) |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (g) | Non-planar so thickness is at least 2 |
| Answer | Marks |
|---|---|
| Hence thickness = 2 | B1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 2.1 | Deducing that thickness 1 or thickness > 1 |
| Answer | Marks | Guidance |
|---|---|---|
| vertex | A | B |
| degree | 3 | 3 |
Question 4:
4 | (a) | e.g. A B F C D H E | B1
[1] | 1.2 | A valid path through 7 of the vertices (no repeats)
4 | (b) | e.g. A B E H G C A | B1
[1] | 1.2 | A valid cycle through 6 of the vertices (no repeats, closed)
4 | (c) | e.g. D and G
have degree sum 2 + 2 = 4 which is less than 8 | M1
A1
[2] | 2.1
2.4 | Identifying any pair of non-adjacent vertices, not including C or H
Demonstrating that sum of vertex degrees is less than 8
4 | (d) | e.g.
D CDH (or reversed)
G CGH (or reversed)
F at least one of FC or FH (or reversed)
so at least one of C and H must be repeated | M1
A1
[2] | 2.1
2.1 | Or equivalent valid explanation of why there cannot be a cycle
through all the vertices without repeating a vertex
Complete valid explanation
4 | (e) | Output: bipartite | M1
A1
[2] | 1.1
1.1 | A, D, E, F, G = and B, C, H =
Leading to conclusion ‘bipartite’
4 | (f) | Graph contains K as a subgraph
3,3
{A, E, F},{B, C, H}
Hence graph is non-planar | M1
B1
A1
[3] | 2.2a
2.2a
1.1 | K only (not ‘graph contains K or K ’)
3,3 3,3 5
Identifying the sets that form K (without D and G)
3,3
Non-planar (or not planar or equivalent) with an attempt at
identifying the sets
4 | (g) | Non-planar so thickness is at least 2
Can be drawn using two planes
e.g.
Drawn on 2 planes so thickness is at most 2
Hence thickness = 2 | B1
B1
[2] | 2.1
2.1 | Deducing that thickness 1 or thickness > 1
Representing the graph using exactly two planes
Using a diagram or described in words (e.g. one graph with all arcs
except CE and a second with just CE)
e.g
Vertices used must be labelled or description must make it obvious
which vertices are connected in each subgraph.
All 13 arcs included once only, and no extras
Conclusion may be implied
For reference:
vertex A B C D E F G H
degree 3 3 5 2 3 3 2 5
vertex | A | B | C | D | E | F | G | H
degree | 3 | 3 | 5 | 2 | 3 | 3 | 2 | 54 A connected graph is shown below.\\
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}
\begin{enumerate}[label=(\alph*)]
\item Write down a path through exactly 7 of the vertices.
\item Write down a cycle through exactly 6 of the vertices.
\item Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
\item Prove that the graph is not Hamiltonian.
The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, (1) and (2).
STEP 1 Choose a vertex and assign it colour (1).\\
STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).\\
STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).\\
STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.\\
STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word "bipartite".\\
Otherwise the graph is not bipartite, output the words "not bipartite".
\item Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
\item Explain what Kuratowski's theorem tells you about the graph.
\item Show that the graph has thickness 2 .
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2022 Q4 [13]}}