﻿ The Four-Color Theorem of Map-Making Proved by Construction

Open Access Library Journal
Vol.03 No.12(2016), Article ID:72664,12 pages
10.4236/oalib.1103089

The Four-Color Theorem of Map-Making Proved by Construction

John W. Oller Jr.

University of Louisiana, Lafayette, USA

Received: November 3, 2016; Accepted: December 6, 2016; Published: December 9, 2016

ABSTRACT

The objective of this paper is to prove by simple construction, generalized by induction, that the bounded areas on any map, such as found on the surface of a sheet of paper or a spherical globe, can be colored completely with just 4 distinct colors. Rather than following the tradition of examining each of tens of thousands of designs that can be produced on a planar surface, the approach here is to all the ways that any given plane, or any given part of a plane, can be divided into an old portion bearing its original color as contrasted with a new portion bearing a different color and being completely separated from the former colored portion. It is shown that for every possible manner of completely carving out any piece of any planar surface by an indexical vector, the adjacent pieces of the map, defined as ones sharing some segment of one of their borders of a length greater than 0, can always be colored with just 4 colors in a way that differentiates all the distinct pieces of the map no matter how complex or numerous the pieces may become.

Subject Areas:

Discrete Mathematics

Keywords:

Four-Color Map Theorem, Proof by Construction, Peircean Exact (Mathematical) Logic

1. Introduction and a Brief Literature Review

Easy to express but difficult to prove, the “four-color map theorem” is a proposition plainly put by Francis Guthrie in 1852. It seemed to be an almost trivial problem for map-making, and though evidently true, it turned out to be more interesting and complex than it seemed on first look [1] - [7] . In its simplest form, the theorem says that “no more than four colors are required to color the regions” of any planar map “so that no two adjacent regions have the same color” ( [6] , p. 1383). The theorem presupposes that corners, consisting of points shared by three or more colored spaces do not qualify as “adjacent” borders or edges. Logically, this is a necessary presupposition so long as any given “corner” shared by two or more colored spaces consists of a single dimensionless point. This is the same as saying that any adjacent border between two distinct regions of the map must have a length greater than zero.

However, proof of the four-color theorem turned out to be more difficult than seemed likely at first blush [1] [6] [7] and even now it ranks higher in complexity than many others including, for instance, Riemann’s Hypothesis [2] [3] . It is not known whether it is possible to meaningfully define a “highest complexity order of well-known mathematical problems” ( [2] , p. 10) or how high in the mix the four-color theorem might rank with respect to such a theoretical limit if one could be defined, but we do know historically that the first satisfactory proof of the four-color theorem was not achieved until 1976, 124 years after it was clearly stated. Also, the first satisfactory proof relied heavily on the brute force of modern computing to examine the multitudinous adjacent pieces of map coloring puzzles that were constructed by combinatory algorithms on a planar surface [1] .

Over the last several decades, it has become increasingly feasible to assess the validity of cumbersome formalized mathematical proofs by taking advantage of the speed, power, and accuracy of modern computing. However, the advantages of automated auditing of formalized proofs, such as the proofs of the four-color theorem, presents special difficulties to human auditors. Efforts along that line have led to a rephrasing of the long- standing question of “artificial intelligence”. Govindarajalulu, Bringsjord, and Taylor put that question like this: “Is it possible to apply computational power to generate entirely new proofs not previously discovered by humans?” ( [8] , p. 2077). Of course, it almost goes without saying that proofs, or audits of proofs, dependent on the brute force of modern computing are probably going to be difficult for slower and more fallible human auditors who are hard-pressed to access, remember, or otherwise carry out very large numbers of computations in whole lifetimes not to mention in reasonable segments of our ordinary wakeful experience [9] [10] . If humans have difficulty checking the computations of a super-computer or a network of such computers, how will it be possible for them to check the computer audit of a proof of one or many difficult formalized proofs dependent on the speed, power, and accuracy of the technology? For that reason, as argued long ago by the Earl of Ockham, by Galileo, and also by C. S. Peirce [11] [12] , simpler theories and simpler proofs are much to be preferred.

Although the four-color theorem is believed to be true, and its complex computer- assisted proofs are believed to be valid, certain conjectures related to that theorem remain unproved and simpler proofs of the four-color theorem itself are still being sought. In 2012 Cooper, Rowland, and Zeilberger took some steps toward what they described as a “language theoretic proof” involving the parsing of binary trees. They argued that within their simple grammar the proposition “that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-co- lorable” and they also supposed that the results they achieved “are a step toward a language theoretic proof of the four color theorem” ( [4] , p. 414). Yet they do not claim to have completed such a proof though it seems that if such a proof can be completed, it may be simpler than the existing computer-assisted proofs.

In the meantime, according to the Web of Science Core Collection, Gonthier’s 2008 computer-assisted proof of the four-color theorem has been cited at least 75 times at the time of this writing (June 14, 2016). Also, continuing interest in proofs of the four- color theorem is shown in the non-linear increase in citations of Gonthier’s proof as shown in Figure 1. More than half (57.33%) of the citing articles referring to that eight- year-old proof (43 of the 75) have appeared in the most recent three and a half years.

Therefore, in light of all the foregoing, a simple constructive proof of the four-color theorem might be of interest. In building the following proof, as in my mathematical proofs about biosemiotic entropy [13] [14] , I follow Peirce. He summed up his method by saying: “I never introduce a distinction without having deduced the necessity for it” ( [15] , p. 340). In applying such a method of “exact logic”, he claimed in 1867 to have proved that “... all mathematical reasoning is diagrammatic and that all necessary rea-

Figure 1. Number of citations appearing in sources both included and not included in the Web of Science Core Collection of Gonthier’s “Formal Proof-The Four Color Theorem” in Notices of the American Mathematical Society, 55(11), 1382-1393.

soning is mathematical reasoning, no matter how simple it may be. By diagrammatic reasoning, I mean reasoning which constructs a diagram according to a precept expressed in general terms, performs experiments upon this diagram, notes their results, assures itself that similar experiments performed upon any diagram constructed according to the same precept would have the same results, and expresses this in general terms. This was a discovery of no little importance, showing, as it does, that all knowledge without exception [including mathematical knowledge] comes from observation” ( [16] , pp. 47-48). Peirce argued that mathematical thinking in consisting of experimentation carried out on diagrams is itself a form of material (empirical) observation. Yet he refused to believe that “mathematics depends in any way upon logic” because he contended “all formal logic is merely mathematics applied to logic” ( [17] , p. volume 4, paragraph 228).

Interestingly, if the proof proposed here bears up under intense critical scrutiny, it will be, I believe, because of the peculiar binary nature of the kinds of sign systems known as indexes in Peircean logic. It is their particular binary character, hinted at in the “step toward a language theoretic proof of the four color theorem” by Cooper, Rowland, and Zeilberger ( [4] , p. 414), I believe, that renders the following proof both rigorous and complete. To help mathematicians who may be unfamiliar with Peircean concepts to understand the proof, it is useful to point out the fact that indexes always aim to separate some entity (or abstract concept) that is singled out for attention, or for coloring in the four-color map problem, from all other things (or from all other concepts) that might have been attended to (or that might be colored distinctly from all adjacent pieces in the four-color map problem).

In the case of map-making, it is the role of every index in a well-formed map to separate any colored space contained within its scope from all other spaces. To accomplish that function, every indexical boundary in any well-formed planar map must be binary in two critical respects: for one, it forms a boundary completely separating (1) its contained space from (2) all other spaces on the map, and, for another, if during the construction of the map, the completed boundary is cut by a new index so as to form a new and distinct space on the map, the index in question can only possess at most two ends: (1) the beginning end and (2) the final end of the cut that joins its own beginning or some other edge of an existing boundary to fully enclose the new bounded space on the map. It is necessary that the two ends of the new space meet up with each other by being connected through the completed boundary enclosing the new space. If these binary aspects of every index that might be used to create a new space on a colored map are kept in mind, that peculiar binary nature will assist the reader in understanding the rigor and completeness of the following proof.

2. A Simple Indexical Proof of the Four-Color Theorem by Construction

To begin, we can color any bounded surface in 1 color as in Figure 2. Next, we can cut the existing map into two completely bounded and separated pieces with an index that

Figure 2. Any planar surface can be colored completely in just one color.

defines a new space, a completely bounded island in the plane that is distinct from the rest of the plane. Provided the new island does not cover the whole map, in which case only 1 color would be needed, only 2 colors will be required to differentiate the emergent new island and it may take any shape whatsoever. For simplicity’s sake, however, on the map abstracted in the diagram of Figure 2, the new island is represented by the smaller red circle that is cut out of the whole, but absolutely any closed planar polygon would give exactly the same result with respect to coloring the whole map so that all its adjacent areas are distinguished. Only 2 colors would be required.

Given such a 2-colored map consisting of two colored spaces in any possible arrangement, if a new island (of any shape whatsoever) should emerge completely contained within either of the existing colored spaces, as abstracted with circles in the diagram of Figure 3, the color not overlapped could in all possible cases be used as in Figure 4, A or B, so that all adjacent areas on the whole map could be distinguished by only 2 colors. If however the emerging island (of any shape whatsoever) should overlap both the existing colored spaces (also irrespective of its or their shapes), as abstractly shown in Figure 5, only 3 colors would be needed to color each bounded portion of the whole map.

Given a map in any shape divided into three adjoining spaces colored distinctly in 3 colors, suppose that a new island completely contained within any of the existing colored spaces should emerge as shown by the black circles added in three places in Figure 6. In any such case, regardless which of the existing colored spaces might be selected for the new island (and irrespective of the shape of either the old or new bounded space), if the new polygon (having any number of corners up to an infinite number) is completely contained within any one of the existing spaces, there must remain 2 color choices to differentiate the new island from all adjacent spaces as shown abstractly in Figure 6. But suppose the new island should partially overlap all three of the existing colored spaces in any configuration as abstracted in Figure 7. In that case, a

Figure 3. An emergent island anywhere on the map requires a second color.

(a) (b)

Figure 4. An emergent island contained in an existing colored space does not require any new color.

Figure 5. An emergent island overlapping two existing colors requires a third color.

Figure 6. An emergent island within any of the existing colored spaces does not require any new color.

Figure 7. An emergent island overlapping three existing colors requires a fourth color.

4th color would be needed, but with just 4 colors all of the adjacent bounded parts of the whole surface could be colored and would be differentiated in all possible cases constructed in the manner described irrespective of the shapes of the adjoining spaces filling the entire map.

Yet, suppose next that a new island should emerge anywhere on the now four-co- lored map: 1) If the new island (entirely irrespective of its shape) should be completely contained within any distinctly colored area of the map, any of the other 3 contrasting colors could be chosen to differentiate that island (exactly as already shown in the abstracted diagrams in Figure 3, Figure 4, and Figure 6 which together cover all possible cases up to that level of complexity); 2) if the newly emergent island should overlap 2 existing colored areas, either of the 2 non-overlapped colors could be chosen to differentiate the new island for all possible cases of that complexity (as abstracted in the diagram of Figure 5); 3) if the new island should overlap 3 existing colored spaces, irrespective of its shape, the 4th color could be chosen for all possible cases of that complexity (as abstracted in Figure 7). Finally, we can prove that if the new island should overlap any number of spaces already colored by at least one of the 4 distinct colors, it must always be possible to recolor the whole map using no more than the 4 existing colors so as to differentiate the new space from all the existing adjacent colored spaces no matter how numerous the overlapped spaces might be.

To see that this must be so for all possible cases, consider first the four corners problem illustrated in the actual map of the United States at the intersection of Arizona, Utah, Colorado, and New Mexico, as shown in Figure 8. The proof that an emergent island overlapping all four existing colored spaces can always be differentiated from them by recoloring all or some portions of the map can be demonstrated by imagining a map of the sort abstractly represented in Figure 9 where, to illustrate the following

Figure 8. The problem of an island emerging so that it overlaps at least 4 existing colored spaces as found in the map of the United States at the Four Corners Monument.

Figure 9. An emergent island covering all four existing colors that, at first look, might seem to require a fight color.

solution, exactly 4 colored spaces share a border with the new island colored in black. But let the new island be transformed into a different shape by cutting to its center and stretching it into a ribbon as suggested in Figure 10. We can, in principle, always do this kind of transformation at any nexus of borders of any given newly created polygon. This expansion is possible for the entire polygon regardless of the number of corners it may share with other colored spaces at its perimeter. To prove this is so, imagine the point where the borders of Arizona, Utah, Colorado, and New Mexico meet at or near the Four Corners Monument as shown in Figure 8. By expanding the point at any such corner into a circle of radius greater than zero, or into a polygon of any number of sides, as abstractly suggested by the black circle in Figure 9, we discover the necessary outcome that every adjacent surface sharing an arc of the circle, or any segment of any polygon, no matter how small that arc or segment might be, can only be bordered by a maximum of 3 spaces as shown in Figure 11 and Figure 12 (see the inside of each of the dashed circles) thus leaving a 4th color to differentiate the new island. No more than 2 colored spaces can share a common border with the new island (colored in black and numbered 5) at any corner of its entire perimeter. The reason this must be so for all possible cases is bound up in the binary nature of an index.

If the end points of the cutting index the one that differentiates a new island or that divides an existing colored piece of the map into an old and a new piece should meet each other without crossing any border of any other colored space on the map, then the new island irrespective of its shape can take any of the 3 remaining colors that contrast with that of the colored space inside which the new island appears. If however, the indexical line should divide any existing colored space by intersecting any pair of existing borders, corners, or any border and corner in combination, the newly carved out out space can always be distinguished with a 4th color, exactly as shown in the abstracted diagrams of Figure 11 and Figure 12.

5

Figure 10. A polygon of any shape can be cut at some part of its border and straightened into a ribbon as suggested abstractly by the cutting of a circle to its center and stretching it into a ribbon while maintaining the sequence of points along its border including any that may be shared by an adjacent but distinctly colored part of the map.

Figure 11. However, given that no more than three adjacent colors can exist at any point (corner) shared by three or any number of adjacent spaces having such an un-extended corner point (one of 0 dimensionality), exactly four colors are sufficient to color any planar surface whatsoever as suggested in the following figure.

Figure 12. Four colors are sufficient to color any emergent island covering any point shared by 3 or more adjacent already colored spaces.

The constructive proof is produced by straightening the abstracted border of the new island whether it be a perfect circle as suggested abstractly in the diagram of Figure 10, or whether it be a polygon with any number of its own internal corners which may or may not be shared by more than one of the other colored spaces on the map. The constructive proof only requires that the border of any newly constructed island (whether it be a perfect circle or a polygon of any number of sides) that may be added to the map be transformed into a ribbon (a binary index). As shown in Figure 11 and Figure 12 for the case of an island overlapping all four existing colors on the map, by cutting the circle (or any polygon) at some point on its border and straightening it into a ribbon (see Figures 10-12), provided only that adjacent colored spaces are kept in the same relative positions moving away from the cut in either direction, no corner bordering the new island at any point on its perimeter (now stretched into a line segment as abstractly shown in Figure 12) can be bordered by more than 2 distinct adjacent spaces. Moreover, given that any adjacent pair of corners marks the division of at most 3 spaces on the perimeter of the new island at any junction of 2 or more adjacent spaces as shown abstractly in Figure 12 the newly formed island can always be colored by a 4th color rendering the new construction colorable by a maximum of 4 colors.

Further, given that it is not possible to construct any additional spaces in any portion of any planar map by any method other than the ones already examined, the proof is complete. To fault the proof it would be necessary for any would-be critic to show by any method of construction how it is possible to make an indexical cut of any bounded portion of a map in a manner that divides an existing space so as to produce a nexus of 2 adjacent corners on the perimeter of that new island that mark the intersection of more than 3 spaces with boundaries adjacent to the new island. But, that cannot be done, because we have already examined all of the possible ways of dividing any colored space on any map into an old space and a new one. We have also examined the corner problem in a manner showing that any number of corners joined at any single point on the map, or at any number of points on the perimeter of any given piece of the map, old or new, can always be resolved as already shown by the foregoing construction. Also, the simple proof presented here suggests that a “language theoretic proof” along the lines of [4] can probably be completed.

3. Conclusion

By induction from the foregoing constructions, it follows that any map, including the infinitely complex sorts constructed in the complex number plane as differentiated into the fractal patterns of the Mandelbrot set, sampled in Figure 13, can also be colored so that all of its bounded spaces are differentiated by no more than 4 colors.

Figure 13. A bit of the Mandelbrot Set in the complex number plane. Reprinted under the GNU Free Documentation License, Version 1.2 retrieved at https://commons.wikimedia.org/wiki/File:Mandel_zoom_14_satellite_julia_island.jpg on May 7, 2016.

Competing Interests

The author declares that he has no competing interests.

Cite this paper

Oller Jr., J.W. (2016) The Four-Color Theorem of Map-Making Proved by Construction. Open Access Lib- rary Journal, 3: e3089. http://dx.doi.org/10.4236/oalib.1103089

References

1. 1. Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part I: Discharging. Illinois Journal of Mathematics, 21, 429-490.

2. 2. Burgin, M., Calude, C.S. and Calude, E. (2011) Inductive Complexity Measures for Mathematical Problems. Centre for Discrete Mathematics and Theoretical Computer Science.

3. 3. Calude, C.S. and Calude, E. (2010) The Complexity of the Four Colour Theorem. LMS Journal of Computation and Mathematics, 13, 414-425.
https://doi.org/10.1112/S1461157009000461

4. 4. Cooper, B., Rowland, E. and Zeilberger, D. (2012) Toward a Language Theoretic Proof of the Four Color Theorem. Advances in Applied Mathematics, 48, 414-431.
https://doi.org/10.1016/j.aam.2011.11.002

5. 5. Dvorák, Z., Kawarabayashi, K. and Král, D. (2016) Packing Six T-Joins in Plane Graphs. Journal of Combinatorial Theory, Series B, 116, 287-305.
https://doi.org/10.1016/j.jctb.2015.09.002

6. 6. Gonthier, G. (2008) Formal Proof—The Four Color Theorem. Notices of the American Mathematical Society, 55, 1382-1393.

7. 7. Wilson, R. (2002) Four Colors Suffice. How the Map Problem Was Solved. Princeton Science Library, Princeton University Press, Princeton.

8. 8. Govindarajalulu, N.S., Bringsjord, S. and Taylor, J. (2015) Proof Verification and Proof Discovery for Relativity. Synthese, 192, 2077-2094.
https://doi.org/10.1007/s11229-014-0424-3

9. 9. Adams, M. (2016) Proof Auditing Formalised Mathematics—Researcher Publication. Journal of Formalized Mathematics, 9, 3-32.

10. 10. Edwards, C. (2016) Automating Proofs. Communications of the ACM, 59, 13-15.
https://doi.org/10.1145/2892710

11. 11. Peirce, C.S. (1885) On the Algebra of Logic: A Contribution to the Philosophy of Notation. American Journal of Mathematics, 7, 180-202.
https://doi.org/10.2307/2369451

12. 12. Peirce, C.S. (1897) The Logic of Relatives. The Monist, 7, 161-217.
https://doi.org/10.5840/monist18977231

13. 13. Oller, J.W. (2010) The Antithesis of Entropy: Biosemiotic Communication from Genetics to Human Language with Special Emphasis on the Immune Systems. Entropy, 12, 631-705.
https://doi.org/10.3390/e12040631

14. 14. Oller, J.W. (2014) Biosemiotic Entropy: Concluding the Series. Entropy, 16, 4060-4087.
https://doi.org/10.3390/e16074060

15. 15. Peirce, C.S. (1982) The Logic Notebook. In: Fisch, M., Kloesel, C.J.W., Moore, E.C., Roberts, D.D., Ziegler, L.A. and Atkinson, N.P., Eds., Writings of Charles S. Peirce: A Chronological Edition, Indiana University Press, Indianapolis.

16. 16. Peirce, C.S. (1976) The New Elements of Mathematics by C. S. Peirce. Mouton, Hague.

17. 17. Peirce, C.S. (1931) The Collected Papers of C. S. Peirce, 1-8. Belknap Press of Harvard University, Cambridge.