Colouring Planar Graphs

Proposition

Let be planar. Then .

Proof

The average degree of is
Since the average degree is at most
So minimal degree is at most

Proposition

Let be planar. Then admits a colouring.

Proof

Proof by induction.
Let be the vertex of minimum degree in
Then is still planar so has a colouring.
Also is connected to at most vertices in
so we can choose a sixth colour for

Proposition

Let be planar. Then admits a colouring.

Proof

By induction.
Let have degree at most
Then colour in colours.
Let be neighbourhoods of arranged clockwise
WLOG they are all coloured differently,
say by colours respectively.
Consider the connected component of
in the subgraph of consisting of vertices of colours
If is not in that component, then swap colours
and colour by
Otherwise there is a path from to in colours
Do similar for and with colours
The graph is planar, so these two paths intersect
But this is a contradiction.