5 Colour Theorem for Planar Graphs

5 Colour Theorem for Planar Graphs

We have already shown the proof for the 6 Colour Theorem for Planar Graphs, and now we will prove an even stronger result, the 5 colour theorem.

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

Note that the beginning of this proof will be virtually identical to that of the 6 colour theorem for planar graphs.

  • Proof: Let $S(n)$ be the statement that for a connected planar simple graph $G$, the vertices in $G$ can be coloured with $5$ or fewer colours for a good colouring of $G$.
  • Base Step: For $1 \leq n \leq 5$, this is trivially true. A graph on $1$ vertex can easily be coloured with just $1$ colour, while a graph with $5$ vertices can easily be coloured with just $5$ colours for a good colouring.
  • 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 $5$ 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 $5$ or fewer colours still).
  • Once again, suppose we have a graph $G$ on $k$ vertices. We know that a connected planar simple graph $G$ contains a vertex of degree $5$ or less.
Screen%20Shot%202014-04-10%20at%201.58.15%20PM.png
  • Suppose the $v$ has $\deg(v) = 5$. If we delete this vertex and all edges incident with $v$, then by our induction hypothesis the resulting graph has a good $5$ colouring.
Screen%20Shot%202014-04-10%20at%201.58.34%20PM.png
  • Now we reinsert the vertex $v$. Notice that a good $5$-colouring cannot happen if vertex $v$ has neighbours all with different vertex colours since $v$ would then need a $6^{\mathrm{th}}$ colour. We will prove that the neighbours of $v$ cannot all be the same colour now with the following two cases. We will arbitrarily select the red and orange vertices for these cases without loss of generality.
  • CASE 1: If there no is red-orange alternating vertex path starting at the red vertex and ending at the orange vertex, then we can interchange the red vertex with an orange vertex and our proof is complete:
Screen%20Shot%202014-04-10%20at%202.05.11%20PM.png
  • CASE 2: If there is a red-orange alternating vertex path starting at the red vertex and ending at the orange vertex, then inspect the yellow and the green vertices. There cannot be an alternating yellow-green vertex path starting at yellow and ending at green since the red-orange path interrupts this path. Hence the yellow vertex can be interchanged green and the proof is once again complete.
Screen%20Shot%202014-04-10%20at%202.08.23%20PM.png
  • Hence $S(k-1)$ implies $S(k)$. By the principle of mathematical induction, for $n \geq 1$, $S(n)$ is true. $\blacksquare$

We continue forth to acknowledge that there is a $4$ colour theorem for planar graphs. That is, any planar simple graph can have a good $4$-colouring. We will NOT prove this. In fact, this proof is extremely elaborate and only recently discovered and is known as the 4-Colour Map Theorem. We will note that:

Theorem: For a connected planar simple graph $G$, the vertices in $G$ can be coloured with $4$ or fewer colours for a good $4$ (or less) colouring of $G$, that is, a function $f$ exists, $f: V(G) \to \{1, 2, ..., k \}$ where $1 \leq k \leq 4$ such that for every $x, y \in V(G)$, whenever $\{ x, y \} \in E(G)$, $f(x) \neq f(y)$.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License