Take any map — countries, US states, anything. Try to colour it so no two touching regions share a colour. You'll never need more than four colours.
What is the largest number of colours you could ever need to colour any flat map so that no two regions sharing a border have the same colour?
Touching means a shared edge
Two regions 'touch' only if they share a length of border — meeting at a single point doesn't count (think of the four corner states of the USA). That subtlety is exactly why the rule isn't '6 colours' or '7'.
Appel and Haken's 1976 proof was the first famous theorem checked by computer: they boiled the whole problem down to 1,936 unavoidable map fragments and let a machine verify each one.
Draw four countries that all border each other pairwise. Can you do it with five mutually-bordering countries?
The theorem
Proven in 1976 by Appel and Haken — the first major theorem proven by computer. They reduced the problem to checking 1,936 cases, then had a computer verify each.
Three colours are sometimes enough, sometimes not. Four is always enough. It's exact.