Four Color Theorem - Precise Formulation of The Theorem

Precise Formulation of The Theorem

The intuitive statement of the four color theorem, i.e. 'that given any separation of a plane into contiguous regions, called a map, the regions can be colored using at most four colors so that no two adjacent regions have the same color', needs to be interpreted appropriately to be correct. First, all corners, points that belong to (technically, are in the closure of) three or more countries, must be ignored. Without this restriction, bizarre maps (using regions of finite area but infinite perimeter) can require more than four colors.

Second, for the purpose of the theorem every "country" has to be a simply connected region, or contiguous. In the real world, this is not true (e.g., 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:

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; one can construct maps that require an arbitrarily high number of colors. A similar scenario can also be constructed if blue is reserved for water.

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. This graph is planar (it is important to note that we are talking about the graphs that have some limitations according to the map they are transformed from only): it can be drawn in the plane without crossings by placing each vertex at an arbitrarily chosen location within the region to which it corresponds, and by drawing the edges as curves that lead without crossing within each region from the vertex location to each shared boundary point of the region. Conversely any planar graph can be formed from a 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).