| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | September |
| Marks | 13 |
| Topic | Graph Theory Fundamentals |
| Type | Finding variable values in degree sequences |
| Difficulty | Challenging +1.8 This is a multi-part Further Maths question requiring deep understanding of graph theory including Eulerian graphs, degree sequences, planarity (Kuratowski's theorem), and digraphs. Parts (ii)-(iii) require careful proof construction, (iv) demands knowledge of a specialized theorem, and the question tests multiple advanced concepts across 7 parts, making it substantially harder than typical A-level content. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
7 A simply connected graph has 6 vertices and 10 arcs.\\
(i) What is the maximum vertex degree?
You are now given that the graph is also Eulerian.\\
(ii) Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .\\
(iii) Prove that the vertices of degree 2 cannot be adjacent to one another.\\
(iv) Use Kuratowski's theorem to show that the graph is planar.\\
(v) Show that it is possible to make a non-planar graph by the addition of one more arc.
A digraph is created from a simply connected graph with 6 vertices and $10 \operatorname { arcs }$ by making each arc into a single directed arc.\\
(vi) What can be deduced about the indegrees and outdegrees?\\
(vii) If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees?
\section*{OCR}
\section*{Oxford Cambridge and RSA}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q7 [13]}}