בעת שרטוט מפה מדינית, כל שתי מדינות בעלות קו גבול משותף נצבעות בצבעים שונים, כדי שיהיה קל להבחין ביניהן. כדי להוזיל את עלויות הדפוס, נרצה להשתמש במספר צבעים קטן ככל האפשר. לוח שחמט הוא דוגמה למפה שבה כל מדינה גובלת בארבע מדינות אחרות, אולם די בשני צבעים כדי לצבוע את המפה. האם יש מפה שלצביעתה נחוצים שלושה צבעים? ארבעה צבעים? חמישה צבעים?
פתרון
מפה שלצביעתה נדרשים ארבעה צבעים
במפה שבתרשים מופיעות ארבע מדינות, שכל אחת מהן גובלת בכל שלוש שכנותיה, ולכן נחוצים ארבעה צבעים לצביעתה. אם שתיים מהמדינות שבמפה זו יתאחדו, די יהיה בשלושה צבעים לצביעת המפה שתיווצר.
ומה בעניין חמישה צבעים? בכך עוסק משפט ארבעת הצבעים. ההשערה שדי בארבעה צבעים כדי לצבוע כל מפה, מסובכת ככל שתהיה, הועלתה על ידי פרנסיס גאטרי (Francis Guthrie) בשנת 1850, בעת שעסק בצביעת מפה של אנגליה. הוכחה לנכונותה של ההשערה נמצאה רק כעבור 126 שנה, תוך הסתייעות במחשב.
