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.

اخر الاخبار

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

قسم الإعلام يشارك في الاجتماع التحضيري لمناقشة الخطة الإعلامية لزيارة عاشوراء

بحضور متوليها الشرعي.. العتبة العباسية المقدسة تواصل إقامة المجالس الحسينية لإحياء شهر المحرم

قسم الشؤون الفكرية يطلق برنامجه التبليغي في أكثر من 20 دولة إفريقية

شعبتا الخطابة النسوية والتوجيه الديني تواصلان إقامة المجالس الحسينية في مرقد أبي الفضل العباس (عليه السلام)

المزيد

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

دراسة تكشف علاقة خطيرة بين عمر الأم وصحة مولودها

دراسة تحذر.. اضطراب نوم بسيط قد يسبب الموت المبكر ؟

الاستحمام بالماء الساخن.. راحة مؤقتة وأضرار دائمة للبشرة

ماذا يحدث للجسم عند تخطي وجبة الإفطار؟

المزيد

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

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

السد الصيني العملاق يعيق دوران الأرض ويغيّر شكلها ؟

السعودية تطلق 10 تجارب علمية إلى محطة الفضاء الدولية

المزيد

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

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