The Four Color Problem
The Four Color Theorem was proved by means of a computer in 1976, but the Four Color Problem was posed already around 1850, by Francis Guthrie, who also suggested a solution, but never completed a proof. This video follows Guthrie's approach with the help of some graph theory. Correction: Of the two brothers Francis and Frederick Guthrie, Francis was the oldest, not the other way around, as stated at 1:37. Elaboration of 8:50 "On the plain, the triangles rule": By Grötzsch's theorem, every triangle-free planar graph can be colored with three colors. By the Grünbaum-Aksenov Theorem (extending Grötzsch’s Theorem) every planar graph with at most 3 triangles is 3-colorable. The 4-complete graph has exactly 4 triangles and any other 4-chromatic planar graph must have at least as many. Chratrand and Geller showed that every uniquely 3-colorable graph with more than 3 vertices contains at least 2 triangles, every uniquely 4-colorable graph is maximal planar, and there is no uniquely 5-colorable planar graph. (A maximal planar graph is a graph that can have no edge added to it without the result becoming non-planar.) All together this means that in a 5-subcritical graph, if the graph is planar, its color identity must be the result of the coloring constrains having propagated through the graph's triangles. There are indeed triangle free 5-subcritical graphs, but these are all non-planar. References Biggs, Norman L. Lloyd, E. Keith, Wilson, Robin J. Graph theory, 1736 – 1936, 1976, Oxford University Press, New York. ISBN 0-19-853916-9 Brændeland, Asbjørn. Color fixation and color identity in 4-chromatic graphs, arXiv:1405.1323 Brændeland, Asbjørn. Color identical pairs in 4-chromatic graphs, arXiv:1402.7368 Brændeland, Asbjørn. Francis Guthrie's approach to The Four Color Problem, arXiv:1804.04658 B. Grünbaum, Grötzsch's Theorem on 3-Colorings, Michigan Math. J. 10 (1963), 303-310. G. Chartrand, D.P.Geller: On Uniquely Colorable Planar Graphs, Combin. Theory 6, 271-278, 1969 Chartrand, G.; Lesniak, L.; Zhang, P. (2011), Graphs & Digraphs, Fifth edition. Chapman & Hall/CRC. ISBN 978-1-4398-2627-0. Grötzsch, H. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1959), 109-120. Moser, L. Moser, W. (1961) “Solution to problem 19”, Can. Math. Bull., 4: 187-189
The Four Color Theorem was proved by means of a computer in 1976, but the Four Color Problem was posed already around 1850, by Francis Guthrie, who also suggested a solution, but never completed a proof. This video follows Guthrie's approach with the help of some graph theory. Correction: Of the two brothers Francis and Frederick Guthrie, Francis was the oldest, not the other way around, as stated at 1:37. Elaboration of 8:50 "On the plain, the triangles rule": By Grötzsch's theorem, every triangle-free planar graph can be colored with three colors. By the Grünbaum-Aksenov Theorem (extending Grötzsch’s Theorem) every planar graph with at most 3 triangles is 3-colorable. The 4-complete graph has exactly 4 triangles and any other 4-chromatic planar graph must have at least as many. Chratrand and Geller showed that every uniquely 3-colorable graph with more than 3 vertices contains at least 2 triangles, every uniquely 4-colorable graph is maximal planar, and there is no uniquely 5-colorable planar graph. (A maximal planar graph is a graph that can have no edge added to it without the result becoming non-planar.) All together this means that in a 5-subcritical graph, if the graph is planar, its color identity must be the result of the coloring constrains having propagated through the graph's triangles. There are indeed triangle free 5-subcritical graphs, but these are all non-planar. References Biggs, Norman L. Lloyd, E. Keith, Wilson, Robin J. Graph theory, 1736 – 1936, 1976, Oxford University Press, New York. ISBN 0-19-853916-9 Brændeland, Asbjørn. Color fixation and color identity in 4-chromatic graphs, arXiv:1405.1323 Brændeland, Asbjørn. Color identical pairs in 4-chromatic graphs, arXiv:1402.7368 Brændeland, Asbjørn. Francis Guthrie's approach to The Four Color Problem, arXiv:1804.04658 B. Grünbaum, Grötzsch's Theorem on 3-Colorings, Michigan Math. J. 10 (1963), 303-310. G. Chartrand, D.P.Geller: On Uniquely Colorable Planar Graphs, Combin. Theory 6, 271-278, 1969 Chartrand, G.; Lesniak, L.; Zhang, P. (2011), Graphs & Digraphs, Fifth edition. Chapman & Hall/CRC. ISBN 978-1-4398-2627-0. Grötzsch, H. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1959), 109-120. Moser, L. Moser, W. (1961) “Solution to problem 19”, Can. Math. Bull., 4: 187-189