Grafer och nätverkThe Four Colour Theorem

Alla dessa kartor kan färgas med bara fyra olika färger, men det är inte svårt att föreställa sig att andra, mycket komplicerade kartor kan behöva många fler färger. I själva verket behöver vissa kartor minst fyra färger, när de innehåller fyra länder som alla är kopplade till varandra.

Som tidigare kan vi konvertera en karta med länder och gränser till en plan graf: varje land blir ett toppunkt en kant ett ansikte och länder som delar en gräns ha samma färg kopplas ihop med en kant:

Nu vill vi färga vertikorna på en graf, och två toppar måste ha en annan färg om de är anslutna i en kant.