Chapter 41. Graph Coloring of Planar Graphs

Graph coloring assigns labels, called colors, to the vertices of a graph so that adjacent vertices receive different colors. For planar graphs, coloring has a special geometric interpretation: it models the coloring of regions on a map. Two regions that share a boundary segment must receive different colors. Regions that meet only at a point may receive the same color.

The central fact is that planar graphs require only a small number of colors. Every planar graph is four-colorable, and the easier five-color theorem gives a useful proof technique based on Euler’s formula. The four-color theorem states that every planar graph can be vertex-colored with at most four colors.

41.1 Vertex Coloring

Let $G = (V,E)$ be a graph. A proper vertex coloring of $G$ is a function

such that whenever $uv \in E$,

The least number of colors needed for a proper vertex coloring is called the chromatic number of $G$. It is denoted by

Thus

means that $G$ can be properly colored with at most $k$ colors.

For planar graphs, the basic question is:

The answer is $4$.

41.2 Maps and Planar Graphs

The map-coloring problem can be translated into graph theory. Each region of a map becomes a vertex. Two vertices are joined by an edge when the corresponding regions share a boundary segment. The resulting graph is planar. A proper vertex coloring of this graph is exactly a coloring of the map in which adjacent regions receive different colors.

This translation is important because it removes geometry that is not essential. The shape, size, and position of regions do not matter. Only adjacency matters.

In this way, a problem about maps becomes a problem about planar graphs.

41.3 The Four-Color Theorem

The four-color theorem states:

Every planar graph has a proper vertex coloring using at most four colors.

Equivalently,

This theorem is best possible. The complete graph $K_4$ is planar and requires four colors. Since every pair of vertices in $K_4$ is adjacent, no two vertices can share a color. Hence

Therefore the bound $4$ cannot be lowered to $3$.

The four-color theorem has a famous history. The first correct proof was completed in 1976 and used computer assistance.

41.4 Why Euler’s Formula Gives Six Colors Easily

Euler’s formula implies that every simple planar graph has a vertex of degree at most $5$.

To see this, suppose every vertex had degree at least $6$. Then the sum of degrees would satisfy

By the handshaking lemma,

So

and therefore

But every simple planar graph with $v \geq 3$ satisfies

These two inequalities are incompatible. Hence every simple planar graph has at least one vertex of degree at most $5$.

This degree bound is the basic input for coloring planar graphs.

41.5 The Six-Color Theorem

The six-color theorem states that every planar graph can be colored with at most six colors.

The proof is by induction on the number of vertices.

For the base case, a graph with one vertex is clearly colorable with six colors.

Assume every planar graph with fewer than $n$ vertices is six-colorable. Let $G$ be a planar graph with $n$ vertices. By the degree bound above, $G$ has a vertex $v$ with

Remove $v$ from $G$. The remaining graph $G-v$ is still planar, so by induction it has a proper coloring using at most six colors.

Now put $v$ back. The vertex $v$ has at most five neighbors. These neighbors use at most five colors. Since six colors are available, at least one color remains unused among the neighbors of $v$. Assign that color to $v$.

The resulting coloring is proper. Therefore every planar graph is six-colorable.

41.6 The Five-Color Theorem

The five-color theorem improves the previous result:

Every planar graph has a proper vertex coloring using at most five colors.

This theorem is weaker than the four-color theorem, but its proof is much simpler. It was proved by Percy John Heawood in 1890 after he found a flaw in Kempe’s attempted proof of the four-color theorem.

The proof again uses induction and the fact that every simple planar graph has a vertex of degree at most $5$. The only difficult case occurs when the removed vertex has exactly five neighbors and those five neighbors use all five colors.

41.7 Kempe Chains

A Kempe chain is a connected component of the subgraph induced by two colors.

Suppose a graph has been colored with colors

Choose two colors, say $1$ and $3$. Look only at vertices colored $1$ or $3$. The connected components of this induced subgraph are called $(1,3)$-Kempe chains.

Inside one such component, switching color $1$ to color $3$ and color $3$ to color $1$ preserves proper coloring. Adjacent vertices still have different colors, because the switch only exchanges the two colors within the component.

Kempe chains are the key recoloring tool in the five-color theorem.

41.8 Proof Idea of the Five-Color Theorem

Let $G$ be a planar graph. Use induction on the number of vertices.

Choose a vertex $v$ of degree at most $5$, and remove it. By induction, $G-v$ has a proper coloring using five colors.

If the neighbors of $v$ use at most four colors, then one of the five colors is unused among them. Assign that color to $v$.

The only hard case is when $v$ has exactly five neighbors and they use all five colors. In a planar embedding, list the neighbors of $v$ in cyclic order:

Suppose their colors are

in that order.

Consider the subgraph using only colors $1$ and $3$. If $v_1$ and $v_3$ are in different $(1,3)$-Kempe chains, switch colors $1$ and $3$ on the chain containing $v_1$. Then color $1$ disappears from the neighborhood of $v$, so $v$ can be colored $1$.

If $v_1$ and $v_3$ are in the same $(1,3)$-Kempe chain, then there is a path from $v_1$ to $v_3$ using only colors $1$ and $3$. Together with the edges $vv_1$ and $vv_3$, this path forms a closed curve. By planarity, it separates $v_2$ from $v_4$. Therefore $v_2$ and $v_4$ cannot be connected by a Kempe chain using colors $2$ and $4$.

So switch colors $2$ and $4$ on the chain containing $v_2$. Then color $2$ disappears from the neighborhood of $v$, and $v$ can be colored $2$.

Thus in every case the coloring extends to $v$. This proves the five-color theorem.

41.9 Why the Same Argument Does Not Prove Four Colors

The Kempe-chain method was originally proposed as a proof of the four-color theorem. The flaw is that the recoloring choices can interfere with one another when only four colors are available. Heawood identified the error and salvaged the argument to prove the five-color theorem.

The difference is structural. With five colors, the degree-at-most-five vertex gives enough room to use pairs of nonadjacent neighbors in the cyclic order. With four colors, a vertex of degree $5$ may still appear, and the same simple induction no longer works.

The four-color theorem requires deeper structural analysis.

41.10 Coloring and Cliques

A clique is a set of vertices that are pairwise adjacent. If $G$ contains a clique of size $r$, then

Planar graphs cannot contain $K_5$, because $K_5$ is nonplanar. Therefore a planar graph has no clique of size $5$.

This fact alone does not prove four-colorability. In general, a graph can require many colors even when it has small cliques. However, for planar graphs, topology imposes stronger restrictions than clique size alone.

The graph $K_4$ shows that four colors are sometimes necessary. Since $K_4$ is planar and complete,

41.11 Outerplanar and Bipartite Cases

Special classes of planar graphs have stronger coloring bounds.

A bipartite planar graph has chromatic number at most $2$. Its vertices can be divided into two parts, and every edge joins one part to the other.

An outerplanar graph is a planar graph that can be embedded so that all vertices lie on the outer face. Every outerplanar graph is $3$-colorable. Some require three colors, such as a triangle.

Trees are even simpler. Every tree with at least one edge is bipartite, so it is $2$-colorable. A single isolated vertex is $1$-colorable.

41.12 Summary

Graph coloring of planar graphs grew from the problem of coloring maps. The translation is direct: regions become vertices, shared boundaries become edges, and map coloring becomes proper vertex coloring.

The main results are:

The six-color theorem follows quickly from Euler’s formula. The five-color theorem adds Kempe-chain recoloring. The four-color theorem gives the sharp bound, since $K_4$ is planar and requires four colors.

Planar graph coloring is a central meeting point of topology, combinatorics, and algorithms. It shows how constraints from planar embeddings force strong restrictions on purely combinatorial behavior.