📂Graph Theory

Four Color Map Problem

Buildup

The Four Color Map Problem asks whether four colors are sufficient to color any given map so that adjacent regions are distinguishable. It might seem like complex maps require more colors, but since only adjacent regions need to be different, it’s not as many as one might think. For example, the following is a world map colored with just $4$ colors.

Historically, the Four Color Map Problem was first posed in 1852 by the British botanist Francis Guthrie, who discovered that he could use just four colors to distinguish between different counties on a map of England, and asked his teacher, De Morgan—famous for De Morgan’s Theorem—if it could be proven mathematically. The problem was first seriously addressed academically in a paper by Arthur Cayley in 1879. The Four Color Problem is mathematically posed as follows:

Is every map $4$-colorable?

In mathematics, specifically in graph theory, a map is defined as a $3$-connected planar graph.

Subsequently, in 1879 Alfred Kempe and in 1880 Peter Tait claimed to have proven the Four Color Theorem, but each of their proofs was found to have an error 11 years later by Percy Heawood and Julius Petersen respectively. Heawood instead proved the Five Color Theorem, which states that any map can be colored with $5$ colors.

The Four Color Problem may seem simple at a glance, but this ‘any map’ condition is not as trivial as it may seem. Reducing just one color from the Five Color Theorem introduced a plethora of possible cases, which hindered the proofs. In 1976, Appel and Haken simplified the shapes of maps to a finite number of cases and examined all these cases using a computer, thereby solving the Four Color Problem.

Appel-Haken Four Color Theorem ¹

Every map is $4$-colorable.

Significance

The computer-aided proof was highly controversial at the time and has faced significant criticism since then. To those enchanted by the beauty of pure mathematics, checking 1936 cases one by one may not seem particularly ‘mathematical,’ and some have questioned whether it can truly be called a proof. However, Appel and Haken’s proof is recognized as the first solution to a problem that had puzzled experts for exactly 100 years.