6 Colour Theorem for Planar Graphs

Theorem 1: For a connected planar simple graph $G$, the vertices in $G$ can be coloured with $6$ or fewer colours for a good $6$ (or less) colouring of $G$, that is, a function $f$ exists, $f: V(G) \to \{1, 2, 3, ..., k \}$ where $1 \leq k \leq 6$ such that for every $x, y \in V(G)$, whenever $\{ x, y \} \in E(G)$, $f(x) \neq f(y)$.

• Proof: Let $S(n)$ be the statement that for a connected planar simple graph $G$, the vertices in $G$ can be coloured with $6$ or fewer colours for a good colouring of $G$.

• Base Step: For $1 \leq n \leq 6$, this is trivially true. A graph on $1$ vertex can easily be coloured with just $1$ colour, while a graph with $6$ vertices can easily be coloured with just $6$ colours for a good colouring (recall that we restrict ourselves to simple graphs).

• Induction Step: Suppose that for all $k \geq 2$, $S(k - 1)$ is true. That is, for all connected planar simple graphs on $k - 1$ vertices, we can obtain a good colouring of the vertices in $G$ with $6$ or fewer colours. We want to verify that $S(k)$ is true (that for all connected planar simple graphs on $k$ vertices, we can obtain a good colour of the vertices in $G$ with $6$ or fewer colours still).

• Now let $G$ be a connected planar simple graph on $k$ vertices. Recall that a connected planar simple graph $G$ contains a vertex of degree $5$ or less. Suppose the vertex $v$ has $\deg(v) = 5$.

• Now suppose that we remove vertex $v$ and all of the edges incident with $v$. This graph now has less than $k$ vertices, and by our induction hypothesis, we know this resulting graph can be coloured with $6$ or fewer colours.

• Adding vertex $v$ back, we know that the neighbourhood of $v$ contains $5$ members. Hence if we use the $6^{\mathrm{th}}$ colour for vertex $v$, our proof is complete.

• Hence $S(k-1)$ implies $S(k)$. By the principle of mathematical induction, for $n \geq 1$, $S(n)$ is true. $\blacksquare$

In fact, it turns out that for any connected planar simple graph we can colour the vertices with $5$ or fewer colours. As we will soon look at with the 5 Colour Theorem for Planar Graphs proof.