Paper 1, Section II, H

Graph Theory
Part II, 2017

Let GG be a graph of order n3n \geqslant 3 satisfying δ(G)n2\delta(G) \geqslant \frac{n}{2}. Show that GG is Hamiltonian.

Give an example of a planar graph GG, with χ(G)=4\chi(G)=4, that is Hamiltonian, and also an example of a planar graph GG, with χ(G)=4\chi(G)=4, that is not Hamiltonian.

Let GG be a planar graph with the property that the boundary of the unbounded face is a Hamilton cycle of GG. Prove that χ(G)3\chi(G) \leqslant 3.