28 May 2004

Why there are no five-color plane maps:
An essay on graphs, maps and coloring

Arnold R. Post
ArnyP@aol.com

The 4-color problem is to show that adjacent regions in the plane can be distinguished from each other using no more than 4 colors. Non-adjacent regions may or may not be the same color.

This essay has 2 purposes: (1) to explain why departure from the conventional approach to this problem is called for, and (2) to indicate what should replace the conventional approach.

The conventional approach to the problem relies on graph theory, wherein equivalence between points and regions is taken for granted. Endpoints of a line segment are deemed to be adjacent to each other, preventing a line segment from indicating separation.

These notions are based on defining a map to be a graph embedded in a surface. Other notions can be justified by defining a map to be a collection of sovereign areas identified and colored by kings. Later these sovereign areas would be considered as regions when outlined, with regional adjacency across edges and regional separation along edges.

The dual graph of a map-outline carries the weight of the graph-theoretic argument. The dual is constructed by designating a capital point in each region and then defining line segments between the capital points of adjacent regions. Figure 1 (above) illustrates a map of regions with its dual graph of straight lines superimposed.

Leonard Euler (1707-1783) would have noticed that this map-outline contains 6 Regions and five Edges, across which pairs of regions are adjacent. He would have also recognized that, for this type of map in the plane wherein edges do not meet, the expression R - E = 1 is typical. A century later, A. B. Kempe would have noticed that since each edge provides a side for 2 regions, the number of edges is equal to half the number of regional sides.

Since, the sum of regions sorted by sidedness equals the number of regions, Kempe would have derived the relation GRn - (GnR n)/2 = 1 to yield G(2 - n)Rn = 2, where n is the number of a region's sides. Since the expression has a positive value, it is evident that such a map-outline contains at least 2 1-sided regions, suggesting that 2 colors suffice to render adjacent regions in such outlines different in color from each other.

A half century later, H. Whitney would have defined dual graphs. In this case, the dual graph reflects the presence of 1-sided regions by the lack of closed circuits in the graph, making it more obvious that 2 colors suffice for properly coloring such map-outlines. After another few years, I would have noticed that the capital points in the dual graph are all without labels, so that a difference in label at the endpoints of each graphic line segment can be secured by the assignment of the same label to every-other capital point as one travels along the graphic line segments. In other words, if 2 colors suffice for properly coloring a map, no more than 1 color need be assigned to do the job of establishing a difference in color across edges.

In the map-outline of Figure 1, the connection between regions is only across edges, and the connection between capital points in the graph is only along line segments. Thus, the connections of regions and of capital points are both 1-dimensional so that graph and map-outline are in accordance with each other.

Figure 2 shows another map-outline and its dual graph. This outline is regular in that each edge lies between 2 vertices and each vertex is common to the boundaries of 3 and only 3 regions. The outline and graph are, in this case, discordant.

There are 6 pairings of regional adjacency and 6 also of regional separation in the map. In each case, there are 2 ways to get from 1 region in each such pair to the other by way of single edges. 1 can cross the edge where the regions are adjacent; or 1 can proceed along the edge where the regions are separate. For instance, regions A and B are adjacent at the edge where regions C and D are separate. Regions A and B are separate at the edge where regions C and D are adjacent.

There is regional connection both across and along the length of each edge in the map-outline. But in the graph, there is direct connection between capital points only along each line segment. Regional connection in the outline is 2-dimensional. But point connection in the graph is still 1-dimensional. Separation of points A and B in the graph requires 4 line segments giving passage around the C-D line segment by way of the C and D regions, as if edges had no length and regions were nothing but adjacent to each other as in Figure 1.

Edges, representing the frontiers of royal sovereignty, are defined among regions. Line segments are defined between points. It is evident in Figure 1, where no point is defined, that points are not the primitive elements of map-outlines. Regions representing the original royal claims are the primitive elements of map-outlines.
Regular map-outlines and their dual graphs are not equivalent.

Four-colored map outlines are also 3- or 2-colorable.
Map outlines are n-colored if n colors are assigned to them to secure a proper coloring. Obviously, all outlines of 4 regions are 4-colorable, since 4 colors, such as red, yellow, blue and green, may be assigned to their regions in 1-to-1 correspondence.

Figure 3 shows the outline of 4 mutually adjacent, 3-sided regions. To begin with, we will consider it to be properly colored in the colors listed above. Then we pause and consider what's been d1.

Originally, the outline was shown on white paper with black lines indicating regional boundaries, so that all regions were white. Quite obviously, there was no need to assign green to a region. If it had been left white, its color would be different from the colors of the other regions in the map. This color, in this case white, can easily be defined as the color of the absence of assignable colors and be known as the zero color.

It is axiomatic that color may be assigned to surface, which implies that this zero color is inherent in surface, since assignment of a color, particularly a transparent water color on white paper, may create a color difference in the surface. Clearly, no more than 3 colors need be assigned. 4-color maps are also 3-colorable.

As we consider these 3- and 4-colorings, we can note that in each case, each regional color is only present or absent in each and every region of the map-outline. Thus, it is reasonable to label the regional colors with ordered arrays of binary variables. Position in an array is enough to identify a color in the order of counting or assignment, with 1 or 0 sufficient to indicate presence or absence in a region.

Colors, like numbers, have closure. To wit, a combination of colors is a color, e.g., the combination of red and yellow is orange, another color. With numbers, for instance, five and five is ten, another number. A combination of letters, however, may be a word, not another letter, so that letters do not have closure.

The smallest array of binary variables yielding 4 combinations is enough to label the colors in a 4-colored map-outline. An array of 2 such variables is sufficient.

Let's say that 1,0 is assigned to the red region; 0,1 to the yellow region; 1,1 to the blue region; and 0,0 to the green region, as in Figure 4. Such labeling indicates how the map might have been colored by assignment of only red and yellow to yield orange as a combination of red and yellow (replacing blue), and to preserve white as previously suggested. Thus, 2-coloring is feasible for 4-colored map-outlines.

The 4- and 5-color problems

The 5-color problem is to account for the fact that there are no map-outlines in the plane which require at least 5 colors to achieve a proper coloring. The 4-color problem is to demonstrate that 4 colors suffice for proper coloring of any map-outline in the plane. Solution of the 5-color problem should be implicit in solution of the 4-color problem. However, that is not the case, since the current solution of the 4-color problem does not explain why map-outlines requiring 5 colors are absent from the plane.

In regular map-outlines, as previously noted, each edge lies between 2 vertices, and each vertex is common to the boundaries of 3 and only 3 regions. Regular map-outlines are the only 1s that need be considered. (This definition excludes cubic outlines having loops in their dual graphs.)

It can be shown that in regular map-outlines, the edges may be tri-labeled (a,b,c) so that edges at each vertex are different in label. Figure 5 shows such an edge-tri-labeling of the regular map-outline of 7 mutually adjacent regions in the torus or doughnut, proving that edge-tri-labeling in a regular map-outline does not by itself imply a proper 4 coloring of an outline's regions since this outline requires 7 regional colors and its edges are tri-labeled. The inner and outer circles in the figure are not edges but profiles of the toroidal shape. The dashed lines indicate edges in the back side of the doughnut.

Given such an edge-labeling of a regular map-outline and since each vertex connects edges of the 3 labels, no vertex can be the endpoint of a collection of edges having only 2 of the 3 labels. As a result, each of the a-c, b-c, and a-b collections of edges consists of 1 or more circuits established by the tri-labeling and may surround many regions if the circuits partition the surface, as is not the case in Figure 5.

If such circuits do partition whatever surface contains the map-outline, a first color, red, may be assigned within or outside of the b-c circuit(s) of edges and a second color, yellow, may be assigned within or outside of the a-c circuit(s) of edges to yield a proper coloring, i.e., a difference in color across each edge of the outline. There will be a presence and absence of only the first color across every edge b, red-white or orange-yellow; a presence and absence of only the second color across every edge a, yellow-white or orange-red; and a presence and absence of both colors across every edge c, orange-white or red-yellow. Figure 6 provides illustration.

Thus, it follows that 4-colorable map-outlines may appear in any surface, and 5-or-more colorable map-outlines can be found only if some circuits of edges do not partition the surface. A single closed curve, hence any circuit of edges, partitions the plane. Therefore, map-outlines needing 5 or more colors for proper coloring cannot be found in the plane, and 4 colors suffice for properly coloring any map-outline in the plane.

A mechanical analog of this coloring procedure can be secured by imagining that the b and c diagrams of Figure 6 represent different levels in a structure with a semitransparent floor and a transparent floor above it. Diagram d combines diagrams b and c. Illumination from below permits watching the flow of water colors. On the first floor, edges b and c are dams controlling the flow while edges a are slender tubes over or through which the first color, perhaps red, can flow. On the second floor, edges a and c are dams, while edges b are slender tubes through or over which the second color, say yellow, can flow.

In 1977, I brought this possibility to the attention of Philadelphia's Franklin Institute. The project was considered technically feasible and was estimated to cost $3,000. This sum, unfortunately, was more than could be dealt with as an unbudgeted expense. I had discovered the coloring procedure in 1972, but it wasn't until 1998 that I knew why assignments of 2 colors are enough to account for presence and absence of colors in properly colored map-outlines in the plane.

To demonstrate these observations requires, mainly, definition of context within which to define terms and a demonstration that the edges of regular map-outlines may be properly tri-labeled and how to tri-label them.

Copyright 2004 by Arnold R. Post.