Untuk menjawab pertanyaan sederhana ini ternyata memerlukan pergulatan panjang dan dalam krun waktu ratusan tahun – seperti Theorema Terakhir Fermat (TTF), sebelum akhirnya dipecahkan dengan bantuan komputer.

Asal-usul
Pada tahun 1852, Augustus De Morgan mengirim surat kepada Rowan Hamilton yang didalamnya sekilas disebutkan bahwa seorang mahasiswanya, Frederick Guthrie, bertanya tentang kemungkinan mewarnai peta hanya menggunakan empat warna saja. Ternyata upaya untuk memecahkan problem ini melibatkan pemikiran matematikawan ‘kuno’ seperti [Leonhard] Euler yang mencetuskan teori polihedron. Problem menjadi makin marak setelah dicoba dijawab oleh Cayley dengan hasil kurang memuaskan, sebelum menyeberang ke benua Amerika dibawa oleh Sylvester, rekan Cayley.

Di Eropa dan di Amerika, problem ini sama-sama berusaha dipecahkan. Meskipun lambat dan kurang mendapat perhatian seperti halnya TTF, namun tetap ada matematiwan yang terusik untuk memecahkannya. Titik terang mulai muncul pada tahun 1972, setelah terjadi kolaborasi antara Kenneth Appel dan Wolfgang Haken. Mereka berdua terus berusaha keras untuk membuktikan sampai diungkapakn hasil pembuktian pada tahun 1977 bersama dengan John Koch dan dipublikasikan pada Illinois Journal of Mathematics. Tahun-tahun berikutnya, para matematikawan (Thomas Tymoczko dan Ulrich Schmidt) memberi tanggapan bahwa pembuktian itu ternyata salah. Masih belum patah semangat, Appel dan Heken kembali memberikan tanggapan tentang pembuktian yang mereka lakukan pada tahun 1986  dan 1989.

Baru tahun 1994, Neil Robertson, Daniel Sanders, Paul Seymour dan Robin Thomas merombak semua pembuktian empat-warna. Mengikuti metode dari Appel dan Haken, mereka memberikan 633 konfigurasi yang tidak terbantahkan lagi dengan menggunakan bantuan komputer.