Το 1852, ο μαθηματικός Φράνσις Γκάθρι διατύπωσε ένα ερώτημα που προοριζόταν να βασανίζει έκτοτε τους μαθηματικούς: Ποιος είναι ο ελάχιστος αριθμός χρωμάτων που απαιτούνται ώστε καμιά κρατική ή διοικητική περιφέρεια σε έναν χάρτη να μην έχει ίδιο χρώμα με γειτονική της; Στους περισσότερους χάρτες αυτό γίνεται με χρήση 4 χρωμάτων. Θα μπορούσε άραγε να γίνει μόνο με τρία; `Η μήπως κάποιοι χάρτες απαιτούν 5 ή 6 χρώματα; Το πρόβλημα δεν αφορά μόνο τους χάρτες, αλλά οποιαδήποτε επίπεδη επιφάνεια που χωρίζεται σε διακριτές περιοχές. Ως τέτοια περιοχή ορίζεται ένα τμήμα, που το όριό του είναι συνεχές, ενώ δύο περιοχές θεωρούνται γειτονικές, όταν έχουν κοινό σύνορο, όχι όμως όταν έρχονται σε επαφή η μία με την άλλη σε ένα και μόνο σημείο.

Αν υποθέσουμε ότι έχουμε έναν μεγάλο και σύνθετο χάρτη με μερικές χιλιάδες περιοχές. Πόσος χρόνος θα χρειαζόταν για να εξακριβωθεί αν μπορούν γι' αυτόν να χρησιμοποιηθούν μόνο δύο, τρία ή τέσσερα χρώματα; Παρότι η διαδικασία εξακρίβωσης είναι σχεδόν η ίδια με οποιονδήποτε αριθμό χρωμάτων, ο χρόνος που απαιτείται είναι πολύ διαφορετικός.

Για να διαπιστωθεί αν δύο χρώματα είναι επαρκή, απαιτείται χρονικό διάστημα μιας ή περισσότερων ωρών. Πρώτα χρωματίζει κανείς μια περιοχή, π.χ. κόκκινη. Αυτό σημαίνει ότι όλες οι γειτονικές της πρέπει να βαφτούν π.χ. μπλε και οι γειτονικές σε αυτές κόκκινες κ.ο.κ. Μόλις εντοπιστεί κάποια παραβίαση του κανόνα των μη ομοιόχρωμων γειτονικών περιοχών βγαίνει το συμπέρασμα ότι δεν είναι δυνατή η χρήση δύο χρωμάτων, ενώ αν χρωματιστεί και η τελευταία περιοχή χωρίς διένεξη με τον κανόνα, τότε τα δύο χρώματα αρκούν.

Αν υποθέσουμε ότι τα δύο χρώματα δεν είναι αρκετά, η δοκιμή με τρία χρώματα θα κρατούσε ...αρκετά περισσότερο. Οι βδομάδες θα περνούσαν καθώς θα αναζητούνταν μια λειτουργική λύση, το έργο θα έπρεπε να συνεχιστεί από τα παιδιά του ερευνητή και από γενιές ολόκληρες που θα ακολουθούσαν. Ακόμα κι όταν ο Ηλιος θα κατάπινε τη Γη μετά από δισεκατομμύρια χρόνια, η λύση δεν θα είχε βρεθεί. Ο προσδιορισμός αν ένας τυχαίος χάρτης μπορεί να βαφτεί με σχήμα τριών χρωμάτων είναι ένα «πλήρες μη ντετερμινιστικό πρόβλημα πολυωνυμικού χρόνου» (NP-complete). Για τα προβλήματα αυτού του είδους δεν γνωρίζουμε κάποια πιο γρήγορη μέθοδο πέρα από την εξαντλητική (brute-force) αναζήτηση πραγματοποιώντας όλους τους δυνατούς συνδυασμούς. Το πεδίο ελέγχου των αναζητήσεων αυτών διευρύνεται εκθετικά καθώς μεγαλώνει το μέγεθος του προβλήματος. Για έναν μικρό χάρτη με λίγες περιοχές, θα μπορούσαμε να ελέγξουμε κάθε δυνατό συνδυασμό τριών χρωμάτων, μέχρι να βρούμε κάποιον που να λειτουργεί ή να συμπεράνουμε ότι δεν υπάρχει τέτοιος συνδυασμός. Αλλά ο αριθμός των τρόπων που μπορούμε να βάλουμε τρία χρώματα σε χάρτες με χιλιάδες περιοχές είναι τόσο αστρονομικός, που κάνει μάταιη την εξαντλητική αναζήτηση.

Τι συμβαίνει στην περίπτωση των 4 χρωμάτων; Εδώ η απάντηση είναι απλή και απαιτεί μόλις ένα δευτερόλεπτο, όσο χρειάζεται να πει κάποιος «ναι», επειδή κάθε χάρτης μπορεί να χρωματιστεί σωστά χρησιμοποιώντας 4 χρώματα. Το συμπέρασμα αυτό είναι το προβληματικό θεώρημα των τεσσάρων χρωμάτων. Διατυπώθηκε αρχικά ως εικασία από τον Γκάθρι, όταν διαπίστωσε ότι με αυτόν τον αριθμό χρωμάτων μπορούσε να χρωματίσει σωστά τις περιοχές κάθε γνωστού χάρτη, χωρίς όμως να μπορεί να το αποδείξει μαθηματικά. Ηταν σαφές ότι τα τρία χρώματα δεν ήταν πάντα επαρκή, όπως είναι φανερό από το κυκλικό διάγραμμα που δημοσιεύουμε, στο οποίο κάθε περιοχή συνορεύει με όλες τις άλλες.

Ταυτόχρονα, κανείς δεν μπορούσε να βρει έναν χάρτη που απαιτούσε 5 χρώματα. Ο μαθηματικός Αύγουστος ντε Μόργκαν συμπέρανε ότι χρειάζεται να προστεθεί ένα νέο αξίωμα (μαθηματική δήλωση που θεωρείται ορθή χωρίς απόδειξη, από την οποία μπορούν να προκύψουν πιο σύνθετες δηλώσεις, τα θεωρήματα). Ομως, το 1879 εμφανίστηκε μια απόδειξη ότι τα 4 χρώματα αρκούν, η οποία επιβεβαιώθηκε με μια δεύτερη ανεξάρτητη απόδειξη έναν χρόνο αργότερα. Οι μαθηματικοί έπαψαν να ασχολούνται με το πρόβλημα και γύρισαν ο καθένας στην έρευνά του. Οχι όλοι όμως. Εντεκα χρόνια μετά την πρώτη απόδειξη και οι δύο αποδείξεις ανατράπηκαν αφού διαπιστώθηκαν λάθη σε αυτές, με αποτέλεσμα το θεώρημα των 4 χρωμάτων να ξαναγίνει εικασία των 4 χρωμάτων. Ο μαθηματικός που εντόπισε τα λάθη κατάφερε, ωστόσο, να αποδείξει ότι τα 5 χρώματα είναι με βεβαιότητα επαρκή για το γέμισμα οποιουδήποτε χάρτη.

Επί σχεδόν έναν αιώνα, το ερώτημα θα παρέμενε - χρειάζονται 4 ή 5 χρώματα; - και κανείς δεν θα μπορούσε να βρει απάντηση, παρότι κανείς δεν είχε εντοπίσει κάποιον χάρτη που απαιτούσε 5 χρώματα. Επειδή όμως υπάρχει άπειρος αριθμός δυνατών χαρτών, κάτι τέτοιο δεν μπορούσε να αποκλειστεί. Το πρόβλημα ήταν αδύνατο να αντιμετωπιστεί χειρωνακτικά. Ετσι, το 1976, μετά από εκατοντάδες ώρες χρήσης υπολογιστή, ο αλγόριθμος δύο μαθηματικών του Πανεπιστημίου του Ιλινόις εξάντλησε όλες τις δυνατές περιπτώσεις και το θεώρημα των 4 χρωμάτων έγινε το πρώτο θεώρημα που αποδείχτηκε με τη χρήση υπολογιστών, χωρίς αναλυτική μαθηματική απόδειξη.

Το γεγονός προκάλεσε πολλή συζήτηση μεταξύ των μαθηματικών: Μπορεί μια απόδειξη που είναι αδύνατο να ελεγχθεί από τον άνθρωπο, να θεωρηθεί ως απόδειξη; Πολλοί περίμεναν ότι και αυτή η απόδειξη θα καταπέσει, όπως και οι προηγούμενες. Εγιναν πολλές προσπάθειες γι' αυτόν τον σκοπό τις δεκαετίες που ακολούθησαν, χωρίς επιτυχία. Αντίθετα, οι μαθηματικοί απλοποίησαν τη διαδικασία και επιβεβαίωσαν τον κώδικα του προγράμματος. Παρότι το θεώρημα των τεσσάρων χρωμάτων έγινε τελικά αποδεκτό, δεν έχουν πάψει οι προσπάθειες να βρεθεί αναλυτική απάντηση, αφού η εξαντλητική αναζήτηση δεν εξηγεί γιατί οποιοσδήποτε χάρτης μπορεί να χρωματιστεί μόνο με τέσσερα χρώματα.