Skip to main content

Section 5.2 The Chromatic Number of Planar Graphs

One of the original puzzles in graph theory, and a problem that has led to much of modern graph theory, is to determine how many colors are needed to color the regions in a map. For reasonably simple maps, we can construct a planar dual by representing each region as a vertex and making a pair of vertices adjacent in the graph precisely when their corresponding regions share a border. It is easy to convince ourselves that the graph created this way will always be planar. Thus the question of map coloring becomes one of the chromatic number of planar graphs.

This theorem has a long and interesting history, starting with F. Guthrie who first conjectured the theorem in 1852, and culminating in a proof in 1976 by Kenneth Appel and Wolfgang Haken that relied on computer verification. Along the way, Alfred Kempe gave a false proof in 1879 that was accepted for 11 years. Percy John Heawood found the error and salvaged Kempe's proof into the weaker five color theorem.

Obviously the five color theorem is implied by the four color theorem, but given that the proof of the four color theorem is beyond human verification, we will consider the much simpler proof of the five color theorem.

Suppose \(G\) is a planar graph with the fewest vertices such that it cannot be 5-colored. Let \(v_0 \) be a vertex of minimal degree. By Corollary 5.1.7, \(deg(v_{0} )\leq5\text{.}\) If \(deg(v_{0} )\leq 4\text{,}\) then there exists at least one color with which we could recolor \(v_{0}\text{,}\) and \(G\) would be 5-colorable. Then assume \(deg(v_{0} )=5\text{.}\) Acknowledge the neighbors of \(v_{0}\) clockwise by \(N_{G} (v_{0} )=\{v_{1} ,v_{2} ,v_{3} ,v_{4} ,v_{5} \}\) colored \(1,2,3,4,5\text{,}\) respectively. Since \(G\) is the smallest graph that cannot be 5-colored, \(G-v_{0} \) can be 5 colored for all vertices \(v\in G-v_{0} \text{.}\) Let \(H_{13} \) be the induced subgraph of \(G-v_0\) of vertices colored \(1,3\text{.}\) If \(v_{1}\) and \(v_{3}\) are not in the same connected component \(C_{13}\) of \(H_{13}\text{,}\) then we could recolor in such a way that \(v_{1}\) and \(v_{3}\) are colored the same, and could recolor \(v_{0}\) with the leftover color. Then \(v_{1}\) and \(v_{3}\) belong to the same connected component \(C_{13}\) of \(H_{13}\text{.}\) Note that by the same reasoning, \(v_{2}\) and \(v_{4}\) must belong to the same connected component \(C_{24}\) of the induced subgraph \(H_{24}\) of \(G-v_{0}\) of vertices colored \(2,4\text{.}\) But the neighbors \(v_{1} ,v_{2} ,v_{3} ,v_{4} ,v_{5}\) of \(v_{0}\) were acknowledged in clockwise order, so the connected components \(C_{13}\) and \(C_{24}\) must overlap (they cannot share a vertex as no vertices can be dual-colored). But this violates the assumption of planarity of \(G\text{,}\) a contradiction! Thus we have that \(G\) must be 5-colorable.

One of the many interesting outcomes of attempts to prove the four color theorem is a theorem of Tait about the chromatic index of some nice planar graphs. The idea was to use an edge coloring of a map to induce a coloring of its regions.

We consider bridgeless cubic planar graphs and their edge colorings. Here “cubic” means that every vertex has degree 3 (that is, the graph is 3-regular). The “bridgeless” condition just means that there is no edge, the removal of which, disconnects the graph. These planar graphs are precisely the “nice enough” maps that we want to color the regions of.

This is also a theorem we will not prove. The theorem was conjectured as a way to prove the four color theorem as it would imply the four color theorem. Thus no direct proof of the three color theorem is known. However, we can prove that the three color theorem is equivalent to the four color theorem.

First, we establish a nice lemma about coloring some especially nice maps.

Let \(C\) be a simple closed curve in the plane. We will show that \(R^2-C\) has exactly two regions and can therefore be 2-colored. We will first show that \(R^2-C\) has at most two regions. Suppose not, such that their exists points \(c_1, c_2, c_3\) that belong to distint regions of \(R^2-C\text{.}\) This would imply that no continuous line between \(c_1, c_2, c_3\) exists. Further, since \(C\) is the only boundary line in the plane that means the triangulur region formed when connecting \(c_1, c_2, c_3\) can on be crossed twice. This yields a contraction as this would imply that a pair of the points \(c_1, c_2, c_3\) were in the same region. Therefore \(R^2-C\) has at most two regions. Next we will show that \(R^2-C\) is not connected and therefore has at least two regions. Consider a line starting at \(c_1\) on one side of \(C\) and ending on the opposite side at point \(c_2\text{,}\) passing through \(C\) exactly once. By the partity of the simple closed curve, \(C\text{,}\) there does not exist an alternative path from \(c_1\) to \(c_2\) that does not intersect \(C\text{.}\) Therefore \(R^2-C\) has at least two regions. In tandem with the first conclusion, this implies that \(R^2-C\) has exactly two regions and can therefore be 2-colored. This argument can be extended to any finite number or simple closed curves if we again consider the partity created by a simple closed curve. If one is within an odd number of simple closed curves, color that region the first color and if you are within an even number of simple closed curves, color that region with the second color. This will be still yield a region comprised of a finite amount of simple closed curves that only uses two colors.

Let \(G \) be an arbitrary planar graph whose faces can be colored with four colors (call them colors 1,2,3, and 4). Notice that no edge can border more than 2 faces at once. We will show that we can color the edges with three colors (call them color a,b and c) because it is a two dimensional object. Let edges colored a be those that border faces of color 1 and 2 or of color 3 and 4. Notice that these edges will never be adjacent because they are disjoint sets and the colors of faces are not allowed to be adjacent. Let edges colored b be those that border faces of color 1 and 3 or of color 2 and 4. Let edges colored c be those that border faces of color 1 and 4 or of 2 and 3. Note that we have only used 3 colors, and by our coloring no adjacent edges will be the same color. Note also that we have accounted for all edges as we have considered all pairings of the four colors in the face coloring of \(G \text{.}\) Therefore Theorem 5.2.1 is equivalent to Theorem 5.2.3.

To show the other direction, let \(G\) be a bridgeless cubic planar graph whose edges can be colored with three colors. By following a path of two alternating colors, we get a simple closed curve. (e.g. form a path with the first edge color a, the second color b, the third color a, and so on.) If we do this for all pairs of colors we get three simple closed curves. By Lemma 5.2.4, we know that the interior and exterior of the curve can be two colored. By looking at the overlap of our three simple closed curves we can color the graph by assigning a color depending on how many closed curves enclose the region. Further, we know none of the regions within the same number of simple closed curves will intersect. As there are four possible regions (0,1,2 or 3), we only need four colors to color the graph. Therefore Theorem 5.2.3 is equivalent to Theorem 5.2.1.

As a final note, we point out the reasonableness of Tait's attempt at proving the four color theorem via his three color theorem. At the time, Tait conjectured that every three-connected planar cubic graph has a Hamilton cycle. If this conjecture could be proved, then it would be easy to three color the edges of such a graph, thus proving the four color theorem. Unfortunately, the conjecture was eventually proved to be false by Tutte.

Recall that a snark is a cubic graph with chromatic index 4 (and therefore no Hamilton cycle). This is not a counterexample to Tait's conjecture though, since snarks appear to never be planar. In fact, the existence of a planar snark would lead to a counterexample to the four color theorem itself!