The four color proof suffices. (English) Zbl 0578.05022

Appel, K.; Haken, W.

Math. Intell. 8, No. 1, 10-20 (1986).

From the text: ”In order to explain why the proof of the Four Color Theorem is correct we shall try to explain the intuition of the proof and let the reader understand how the proof was obtained and why the type of errors that crop up in the details do not affect the robustness of the proof. In making the argument accessible to the casual reader we will repeat some details that are familiar to those more expert in the field...
Although we were informed of several errors in 1976 by recipients of the preprints (as mentioned above) to our surprise no one brought any further errors to our attention after October 1976, until 1981. In that year, Ulrich Schmidt completed a Diplom Thesis [Überprüfung des Beweises für den Vierfarbensatz. Diplomarbeit, Technische Hochschule Aachen (1982)] on checking our unavoidability proof by hand as well as by computer programs he wrote for that purpose. Since a time limit was imposed on his thesis, Schmidt could only check the \(q(V_ 5)\)-positive situations (i.e. about 40 percent of the total unavoidability proof); the treatment of the \(q(V_ k)\)-positive situations for \(k=7,8,9,10,11\) is still awaiting independent verification. Schmidt found fourteen errors of degree 1 and one of degree 3. The correction of the error of degree 3 was the only error-correction procedure that had to be carried out in the time since our paper has appeared and we present it here as an example...
With these changes no change in U (an unavoidable set of 1825 reducible configurations, which contains a 1478 member subset that is itself unavoidable) is required. Since no one else has communicated any other errors in the published unavoidability proof since 1976 we assume that a misunderstanding of the nature of Schmidt’s work was the source of those rumors that seem to have stimulated so much new interest in our work. We would certainly appreciate independent verification of the remaining 60 percent of our unavoidability proof and would be grateful for any information on further bookkeeping (or other) errors whenever such are found. We have written computer programs preparatory to a thorough computer verification of all of the material in the microfiche supplements. When this is completed we plan to publish an entire emended version of our original proof including the q-positive bookkeeping.”

Reviewer: I.Tomescu

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

planar triangulation; Kempe chain; unavoidable set of reducible; configurations; Four Color Theorem

Citations:

Zbl 0387.05009; Zbl 0387.05010

References:

[1]	F. Allaire, Another proof of the Four Colour Theorem I, Proc. of the Seventh Manitoba Conference on Numerical Mathematics and Computing, Univ. Manitoba, Winnipeg, Man., 1977, pp. 3–72.
[2]	F. Allaire and E. R. Swart, A systematic approach to the determination of reducible configurations in the four-color conjecture, J. Combinatorial Theory(B)25(1978), pp. 339–362. · Zbl 0398.05034 · doi:10.1016/0095-8956(78)90010-2
[3]	K. Appel and W. Haken, Every planar map is four colorable Part I: Discharging, Illinois J. Math.,21(1977), pp. 429–490. · Zbl 0387.05009
[4]	K. Appel, W. Haken and J. Koch, Every planar map is four colorable Part II: Reducibility, Illinois J. Math.21(1977), pp. 491–567. · Zbl 0387.05010
[5]	K. Appel and W. Haken, The solution of the four-color-map problem, Scientific American, September 1977, pp. 108–121.
[6]	G. D. Birkhoff, The reducibility of maps, Amer. J. Math.,35(1913), pp. 114–128. · JFM 44.0568.01 · doi:10.2307/2370276
[7]	K. Dürre, H. Heesch and F. Miehe, Eine Figurenliste zur chromatischen Reduktion, Technische Universität Hannover, Institut für Mathematik, 1977, Nr. 73.
[8]	H. Heesch, Untersuchungen zum Vierfarbenproblem, B-I-Hochschulscripten 810/810a/810b, Bibliographisches Institut, Mannheim/Vienna/Zurich, 1969.
[9]	H. Heesch, Chromatic reduction of the triangulations Te, e = e5 + e7, J. Combinatorial Theory,13(1972), pp. 46–53. · Zbl 0242.05110 · doi:10.1016/0095-8956(72)90007-X
[10]	A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math.,2(1879), pp. 193–200. · doi:10.2307/2369235
[11]	U. Schmidt, Überprüfung des Beweises für den Vierfarbensatz. Diplomarbeit, Technische Hochschule Aachen, 1982.
[12]	W. Stromquist, Some aspects of the four color problem, Ph.D. Thesis, Harvard University, 1975. · Zbl 0313.05109
[13]	W. Tutte and H. Whitney, Kempe chains and the four color problem, Utilitas Math.2(1972), pp. 141–281. · Zbl 0253.05120