| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | March |
| Marks | 12 |
| Topic | Graph Theory Fundamentals |
| Type | Kuratowski's theorem |
| Difficulty | Challenging +1.3 This is a Further Maths discrete mathematics question requiring knowledge of graph theory theorems (Ore's theorem, Kuratowski's theorem, and subgraph identification). Part (i) involves systematic checking of vertex degrees, part (ii) applies Ore's theorem for Hamiltonian cycles, part (iii) requires identifying a Kâ or Kâ,â subdivision, and part (iv) demands careful enumeration to prove non-existence of Kâ. While conceptually accessible to Further Maths students and mostly procedural, it requires multiple specialized theorems and extended verification across 12 marks, placing it moderately above average difficulty. |
| Spec | 7.02i Ore's theorem: sufficient condition for Hamiltonian graphs7.02j Isomorphism: of graphs, degree sequences7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks | Guidance |
|---|---|---|
| Each vertex has degree either 4 or 5. Vertices with degree 4 are A, B and C which are all adjacent. So min \(= 4 + 5 = 9\) | M1, A1 | Degrees are either 4 or 5; A, B, C are adjacent |
| Answer | Marks | Guidance |
|---|---|---|
| Using Ore's theorem, graph is Hamiltonian | B1 | Hamiltonian / Hamilton cycle / cycle through each vertex once |
| Answer | Marks | Guidance |
|---|---|---|
| After contracting ACF. The subgraph on \(\{D, E, H\}\) and \(\{ACF, G, I\}\) is \(K_{3,3}\) | M1, A1, E1 | An appropriate contraction; Appropriate sets; Trying to justify \(K_{3,3}\) or \(K_5\) subgraph (contracting ABC, DE and HI makes \(K_5\)) |
| Answer | Marks | Guidance |
|---|---|---|
| If C is included then \(K_4\) uses three of A, B, F, G but \(\{F, G\}\) is not connected to \(\{A, B\}\) so this is impossible, hence C is not included. If A is included then \(K_4\) uses B, E, H but there is no direct connection between B and F, so A not included. By symmetry B not included. If D is included then \(K_4\) uses three of F, G, H, I but there is no direct connection GI and no direct connection FH, so D is not included. By symmetry E not included. This leaves \(\{F, G, H, I\}\) but there is no direct connection GI (or FH), so this is also impossible | E1, B1, E1, E1, E1 | Considering C; Deducing that C is not included; Considering A or B; Using symmetry to deduce that A and B are not included; Excluding at least two vertices of degree 5; Complete argument |
## (i)(a)
| Each vertex has degree either 4 or 5. Vertices with degree 4 are A, B and C which are all adjacent. So min $= 4 + 5 = 9$ | M1, A1 | Degrees are either 4 or 5; A, B, C are adjacent |
## (i)(b)
| Using Ore's theorem, graph is Hamiltonian | B1 | Hamiltonian / Hamilton cycle / cycle through each vertex once |
## (ii)
| After contracting ACF. The subgraph on $\{D, E, H\}$ and $\{ACF, G, I\}$ is $K_{3,3}$ | M1, A1, E1 | An appropriate contraction; Appropriate sets; Trying to justify $K_{3,3}$ or $K_5$ subgraph (contracting ABC, DE and HI makes $K_5$) |
## (iii)
| If C is included then $K_4$ uses three of A, B, F, G but $\{F, G\}$ is not connected to $\{A, B\}$ so this is impossible, hence C is not included. If A is included then $K_4$ uses B, E, H but there is no direct connection between B and F, so A not included. By symmetry B not included. If D is included then $K_4$ uses three of F, G, H, I but there is no direct connection GI and no direct connection FH, so D is not included. By symmetry E not included. This leaves $\{F, G, H, I\}$ but there is no direct connection GI (or FH), so this is also impossible | E1, B1, E1, E1, E1 | Considering C; Deducing that C is not included; Considering A or B; Using symmetry to deduce that A and B are not included; Excluding at least two vertices of degree 5; Complete argument |
---The graph below connects nine vertices A, B, $\ldots$, H, I.
\includegraphics{figure_2}
\begin{enumerate}[label=(\roman*)]
\item \begin{enumerate}[label=(\alph*)]
\item Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
\item Explain what you can deduce from the result in part (a). [1]
\end{enumerate}
\item Use Kuratowski's theorem to prove that the graph is non-planar. [3]
\item Prove that there is no subgraph of the graph that is isomorphic to $K_4$, without using subdivision or contraction. [6]
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q4 [12]}}