מפת ישובים לפי צבעים. משפט ארבעת הצבעים

ב- הראה פיליפ פרנקלין שעל-פני בקבוק קליין מספיקים ששה צבעים, וב- הראה רינגל שבכל מקרה אחר החסם של היווד הוא מדויק מאז נעשו ניסיונות רבים למצוא הוכחה סטנדרטית יותר, שיכולה לעמוד ל ללא עזרת מחשב
כעת, צביעת המדינות על המפה שקולה לבחירת צבע לכל קודקוד, באופן כזה שלשני קודקודים המחוברים בקשת יש צבעים שונים קל לראות שמשימה זו שקולה לצביעה של מפה כדורית, שגם עבורה מספיקים ארבעה צבעים

משפט ארבעת הצבעים

קמפ הציע שיטה המבוססת על שרשראות של מדינות סמוכות, שאמורה הייתה לאפשר הוספה של מדינה אחר מדינה למפה הצבועה, מבלי להזדקק לצבע חמישי.

משפט ארבעת הצבעים
אנשי תורת הגרפים מכירים הוכחות קלות יחסית לכך שקיימת צביעה ב חמישה צבעים, אבל ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-, והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים
משפט ארבעת הצבעים
לאחר מכן הם הריצו תוכנית במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים
משפט ארבעת הצבעים
ההוכחה נבדקה, והתקבלה על-דעת בני זמנו
ואולם, 11 שנה מאוחר יותר הראה Heawood שההוכחה אינה נכונה דה-מורגן ניסה בלא הצלחה לעניין בנושא מתמטיקאים אחרים, עד שב- הובאה הבעיה לתשומת לבו של , שהציג אותה בפני
Thomas, Efficiently four-coloring planar graphs, Proceedings of the ACM Symposium on the Theory of Computing, 28 1996 , 571-575 האיור משמאל מציג מפה סכמטית של ארבע מדינות, שלכל אחת מהן יש גבול משותף עם כל האחרות

משפט ארבעת הצבעים

בשנת ניתנה הוכחה בעלת אופי דומה על ידי ניל רוברטסון, דניאל פ.

24
משפט ארבעת הצבעים
סנדרס, ורובין תומאס שבה היה די בבדיקה של 633 מפות
משפט ארבעת הצבעים
עם זאת, טופולוגים עסקו גם בשאלה כמה צבעים נחוצים למפה המצוירת על-פני משטחים אחרים, כגון או
משפט ארבעת הצבעים
רוברטסון וחבריו אף מצאו אלגוריתם ריבועי שזמן הריצה שלו פרופורציוני לריבוע מספר הקודקודים לצביעת גרף מישורי בארבעה צבעים