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

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

במסגרת נסיונוניסיונו להוכיח את המשפט, הפיזיקאי הבריטי פיטר טייט [http://users.wpi.edu/~bservat/blanusa08.pdf] הוכיח שצביעת מפות בארבעה צבעים שקולה לטענה הבאה: לכל [[גרף רגולרי|גרף 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, }}.