$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

5.10: Coloring Planar Graphs

Now we return to the original graph coloring problem: coloring maps. As indicated in section 1.1, the map coloring problem can be turned into a graph coloring problem. Figure 5.10.1 shows the example from section 1.1.

Figure 5.10.1. A map and its corresponding graph.

Graphs formed from maps in this way have an important property: they are planar.

Definition 5.10.1 A graph $G$ is planar if it can be represented by a drawing in the plane so that no edges cross.

Note that this definition only requires that some representation of the graph has no crossing edges. Figure 5.10.2 shows two representations of $K_4$; since in the second no edges cross, $K_4$ is planar.

Figure 5.10.2. $K_4$ drawn in two ways; the second shows that it is planar.

The number of colors needed to properly color any map is now the number of colors needed to color any planar graph. This problem was first posed in the nineteenth century, and it was quickly conjectured that in all cases four colors suffice. This was finally proved in 1976 (see figure 5.10.3) with the aid of a computer. In 1879, Alfred Kempe gave a proof that was widely known, but was incorrect, though it was not until 1890 that this was noticed by Percy Heawood, who modified the proof to show that five colors suffice to color any planar graph. We will prove this Five Color Theorem, but first we need some other results. We assume all graphs are simple.