Prove that the vertices of a planar graph can be coloured in (at most) six different colours such that every pair of vertices joined by an edge are of different colours.
Note: a graph is planar if it can be drawn in the plane with no edges crossing. For example, three houses, each of which is connected to three utilities, is not a planar graph.
You may find it useful to use the Euler characteristic: a planar graph with