משפט ארבעת הצבעים – הבדלי גרסאות

[[תמונהקובץ:Fourcolorsmap.png|שמאל|ממוזער|120px|מפה ([[גרף (תורת הגרפים)|גרף]]) הדורשת לפחות ארבעה [[צבע]]ים]]

[[תמונהקובץ:Four Colour Planar Graph.svg|שמאל|ממוזער|240px|מפה עם הגרף הדואלי]]

הקשר בין מפות מישוריות לבין [[גרף מישורי|גרפים מישוריים]] מבוסס על בניית ה[[גרף דואלי|גרף הדואלי]], שהיא בנייה סטנדרטית ב[[תורת הגרפים]]. בגרף המתאים למפה נתונה, כל מדינה מיוצגת על ידי קודקוד, וכל שתי מדינות שלהן יש גבול משותף מחוברות בקשת בין שני הקודקודים המתאימים. משמאל מוצגת דוגמה למפה ולגרף המתאים לה.

במסגרת ניסיונו להוכיח את המשפט, הפיזיקאי הבריטי פיטר טייט{{הערה|[http://users.wpi.edu/~bservat/blanusa08.pdf Blanuˇsa Double]}} הוכיח שצביעת מפות בארבעה צבעים שקולה לטענה הבאה: לכל [[גרף רגולרי|גרף 3-רגולרי]] [[גרף מישורי|מישורי]] [[גרף קשיר|2-קשיר-קשתות]] (כלומר, כזה שנשאר קשיר גם לאחר מחיקת אחת הקשתות) יש [[צביעת קשתות]] (כלומר, התאמה של צבע לכל קשת באופן ששתי קשתות נפגשות מקבלות צבעים שונים) בשלושה צבעים.{{הערה|1=Louis H. Kauffman, [http://www.math.uic.edu/~kauffman/MapReform.pdf Reformulating the map color theorem], Discrete Mathematics, Volume 302, Issues 1-3, 28 October 2005, Pages 145-172, }}

בשנת [[1976]] נעזרו [[וולפגאנג האקן]] ו[[קנת אפל]] מ[[אוניברסיטת אילינוי באורבנה-שמפיין]] בשרשראות של קמפ, כדי להראות שכל מפה אפשרית שקולה לאחת מבין 1,936 מפות שונות. לאחר מכן הם הריצו תוכנית [[מחשב]] במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים. בשנת [[1996]] ניתנה הוכחה בעלת אופי דומה על ידי ניל רוברטסון, דניאל פ. סנדרס, [[פול סימור]] ורובין תומאס שבה היה די בבדיקה של 633 מפות. גם בדיקה זו דרשה הסתייעות במחשב.{{הערה|[http://people.math.gatech.edu/~thomas/FC/fourcolor.html The Four Color Theorem],{{כ}} School of Mathematics,{{כ}} באתר Georgia Tech,{{כ}} 8 בנובמבר 2007}}