# 9.1: Four Color Theorem

- Page ID
- 50961

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \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}}\)

\( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The **Four-Color Theorem** states that in any plane surface with regions in it (people think of them as maps), the regions can be colored with no more than four colors in such a way that two regions that have a common border do not get the same color. They are called *adjacent* (next to each other) if they share a segment of the border, not just a point.[1]

This was one of the first theorems to be proved by a computer, using a *proof** by exhaustion*. In proof by exhaustion, the conclusion is established by dividing it into cases and proving each one separately. The number of cases sometimes may be very large. For example, the first proof of the Four-Color Theorem was a proof by exhaustion with 1,936 cases (in 1976). This proof was controversial because most of the cases were checked by a computer program, not by traditional mathematical arguments. The shortest known proof of the Four-Color Theorem today still has over 600 cases.

Even though the problem was first presented in 1852 as a problem to color __political maps of countries__, mapmakers are not particularly interested in it. According to an article by the math historian __Kenneth May__ , “Maps utilizing only four colors are rare, and those that do usually require only three. Books on cartography and the history of map-making do not mention the four-color property.”

Many simpler maps can be colored using three colors. The fourth color is required for some maps, such as one in which one region is surrounded by an odd number of others, which touch each other in a cycle. One such example is given in the image. The __Five-Color Theorem__ states that five colors are enough to color a map. It has a short, elementary proof and was proved in the late 19th century (__Heawood 1890__). Proving that four colors suffice turned out to be significantly more difficult. A number of false proofs and false counterexamples have appeared since the first statement of the Four-Color Theorem at University College London in England.

To be able to correctly state and solve the problem, it is necessary to clarify some aspects. First, all points that belong to three or more countries must be ignored.

For the purpose of the theorem every "country" has to be a __connected region__, or contiguous. In the real world, this is not true: __Alaska__ as part of the __United States__, __Nakhchivan__ as part of __Azerbaijan__, and __Kaliningrad__ as part of Russia are not contiguous. Because the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map, such as the one shown above: in this map, the two regions labeled *A* belong to the same country and must be the same color. This map then requires five colors since the two *A* regions together are contiguous with four other regions, each of which is contiguous with all the others. If *A* consisted of three regions, six or more colors might be required. In this manner, it is possible to construct maps that require an arbitrarily high number of colors. A similar construction also applies if a single color is used for all bodies of water, as is usual on real maps.

An easier-to-state version of the theorem uses __graph theory__. The __set__ of regions of a map can be represented more abstractly as an __undirected graph__ that has a __vertex__ for each region and an __edge__ for every pair of regions that share a boundary segment.__[3]__ This graph is __planar__, meaning that these edges and vertices can be drawn on paper without any edges crossing each other. A planar graph can be formed from every map in this way. In graph-theoretic terminology, the Four-Color Theorem states that the vertices of every planar graph can be __colored____ __with at most four colors so that no two adjacent vertices receive the same color, or for short, "every planar graph is four-colorable" (__Thomas 1998__, p. 849; __Wilson 2002__).

## Reference

- References (22)

## Contributors and Attributions

Saburo Matsumoto

CC-BY-4.0