McGregor Map

Martin Gardner (1975) played an April Fool's joke by asserting that the map of 110 regions illustrated above (left figure) required five colors and constitutes a counterexample to the four-color theorem (cf. Wilson 2004, pp. 14-15; Chartrand and Zhang, p. 23, 2008; Posamentier and Lehmann, Fig. 1.13, 2013). However, because the four-color theorem is true (though not proved until 1976), the map must be (and is) four-colorable (right figure above), as demonstrated by the explicitly coloring due Wagon (1998; 1999, pp. 535-536), obtained algorithmically using the Wolfram Language.

As stated by Gardner, "As a public service, I shall comment briefly on six major discoveries of 1974 that for one reason or another were inadequately reported to both the scientific community and the public at large. The most sensational of last year's discoveries in pure mathematics was surely the finding of a counterexample to the notorious four-color-map conjecture. That theorem, as all readers of this department must know, is that four colors are both necessary and sufficient for coloring all planar maps so that no two regions with a common boundary are the same color. It is easy to construct maps that require only four colors, and topologists long ago proved that five colors are enough to color any map. Closing the gap, however, had eluded the greatest minds in mathematics. Most mathematicians have believed that the four-color theorem is true and that eventually it would be established. A few suggested it might be Gödel-undecidable. H.S.M. Coxeter, a geometer at the University of Toronto, stood almost alone in believing that the conjecture is false. Coxeter's insight has now been vindicated. In November 1974 William McGregor, a graph theorist of Wappingers Falls, N.Y., constructed a map of 110 regions that cannot be colored with fewer than five colors. McGregor's technical report will appear in 1978 in the Journal of Combinatorial Theory, Series B." (William McGregor is a real mathematician who created the map and gave Gardner permission to use it as an April Fool's prank; MathNexus 2006.)

REFERENCES

Bryant, R. E. "Coloring the McGregor Graph." https://www.cs.cmu.edu/~bryant/boolean/macgregor.html.Chartrand, G. and Zhang, P. Chromatic Graph Theory. Boca Raton, FL: Chapman and Hall/CRC, p. 23, 2008.

Gardner, M. "Mathematical Games: Six Sensational Discoveries that Somehow or Another have Escaped Public Attention." Sci. Amer. 232, 127-132, Apr. 1975.

MathNexus. "Mathematics for April Fool's Day." Mar. 31, 2006.

 https://mathnexus.wwu.edu/archive/news/detail.asp?ID=19.Posamentier, A. S. and Lehmann, I. Fig. 1.13 in Magnificent Mistakes in Mathematics. Amherst, NY: Prometheus Book, 2013.

Wagon, S. "An April Fool's Hoax." Mathematica in Educ. Res. 7, 46-52, 1998.

Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 535-536, 1999.

Wilson, R. Four Colors Suffice : How the Map Problem Was Solved. Princeton, NJ: Princeton University Press, pp. 14-15, 2004.