Uiteraard kun je het vierkleurenprobleem niet oplossen door elke mogelijke kaart in te kleuren, er zijn immers oneindig veel kaarten. Op een handige manier kan het probleem echter zo aangepakt worden dat je maar eindig veel gevallen hoeft te bekijken.
Ga uit van het ongerijmde: stel dat er kaarten bestaan waarvoor vier kleuren niet voldoende zijn, oftewel stel dat er tegenvoorbeelden zijn. Dan moet er ook een tegenvoorbeeld (of meerdere) zijn met een minimum aantal landen, oftewel een kleinste tegenvoorbeeld.
Het bijzondere van een kleinste tegenvoorbeeld is dat als je er een land uit weghaalt, de overgebleven kaart wel vierkleurbaar moet zijn, anders zou je een nog kleiner tegenvoorbeeld te pakken hebben. De aanpak is dan als volgt. Neem zo'n (denkbeeldig) kleinste tegenvoorbeeld. Laat er een bepaald land uit weg, dan is de overgebleven kaart wel vierkleurbaar. Knutsel dan wat met die overgebleven kaart zodat je het ene extra land ook een van de vier kleuren kunt geven. Dan blijkt de kaart dus toch vierkleurbaar te zijn, en hebben we een tegenspraak.
De vraag is welk land je uit het denkbeeldige kleinste tegenvoorbeeld moet weglaten, je mag namelijk niets speciaals over die kaart aannemen. Dat is precies waar we de onvermijdelijke set voor nodig hebben. Hoe het kleinste tegenvoorbeeld er ook uitziet, ergens moet hij namelijk een van de configuraties uit de onvermijdelijke set bevatten. Loop dus de configuraties van de set één voor één langs en laat steeds zien hoe in dat geval de vierkleuring van de kaart zonder die configuratie uitgebreid kan worden tot een vierkleuring van de kaart met die configuratie er weer in. Lukt dit, dan zeggen we dat die specifieke configuratie gereduceerd kan worden. Als alle configuraties uit de onvermijdelijke set gereduceerd kunnen worden, kan er dus geen tegenvoorbeeld bestaan, en zijn dus alle kaarten vierkleurbaar.

Figuur 3 Het 'bewijs' van Kempe: twee mogelijkheden los/vast.