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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

لتوثيق التراث العلمي.. وفد قسم شؤون المعارف يلتقي عددًا من أعلام مدينة النجف

قسم الشؤون الفكرية ومؤسسة الشهداء يبحثان سبل تعزيز التعاون في برامج الذاكرة الوطنية

المجمع العلمي يقيم دورته التطويرية الثالثة لإعداد أساتذة الدورات الصيفية في صلاح الدين

قسم التطوير يقدم ورشة عن التغيرات الاجتماعية وتأثيرها على الهوية الثقافية في جامعة القادسية

المزيد

الآخبار الصحية

طبيب يكشف تأثير برودة الشتاء على النوم

دون أن تعلم.. 10 عادات يومية تسرع شيخوخة جسمك

تقرير: النيكوتين خطر على القلب مهما كانت الطريقة

أيهما أفضل لصحتك.. زبدة الفول السوداني أم النوتيلا؟

المزيد

الآخبار التكنلوجية

السعودية تدشن أكبر نظام لتخزين الكهرباء بالبطاريات في العالم !

بأمر تنفيذي.. ترامب يؤكد هدف عودة الأميركيين إلى القمر في عام 2028

بعيدا عن البشر.. "قتال جوي في الفضاء" بين أميركا والصين

كشف مذهل في قاع "برمودا" !

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength