Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-1/16h/solution
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 1 16H Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-05
Let be a longest path in the finite simple graph. Every neighbour of either endpoint lies on it. Among indices , consider those with edges and those with edges . Their cardinalities are the endpoint degrees, whose sum is at least , exceeding the available indices. They intersect, producing the cycleEvery connected component has at least vertices, so the graph is connected. If , an edge joins a vertex outside this cycle to it, and breaking the cycle there gives a longer path, a contradiction. Hence and this is a Hamilton cycle, proving Dirac theorem.
The complete graph is planar, has chromatic number four and a Hamilton cycle. Adding one leaf attached to one of its vertices preserves planarity and chromatic number four but prevents a Hamilton cycle, since a leaf has degree one.
For the last claim, the given plane embedding has all vertices on the outer cycle. Add noncrossing diagonals until its polygonal interior is triangulated. A triangulated polygon has a vertex incident with only its two boundary neighbours: for example the dual graph of its triangles is a tree and a leaf triangle supplies an ear. Remove this vertex. Inductively three-colour the smaller triangulated polygon, starting with a triangle. The removed vertex's neighbours are adjacent and have different colours, so it can receive the third. Restriction to the original graph givesThis uses the specified embedding, not the false assertion that every planar Hamiltonian graph is three-colourable; is already a counterexample to that broader assertion.
New to topics? Read the docs here!