7 A simply connected graph has 6 vertices and 10 arcs.
- What is the maximum vertex degree?
You are now given that the graph is also Eulerian.
- Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
- Prove that the vertices of degree 2 cannot be adjacent to one another.
- Use Kuratowski's theorem to show that the graph is planar.
- 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.
- What can be deduced about the indegrees and outdegrees?
- If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees?
\section*{OCR}
\section*{Oxford Cambridge and RSA}