What exactly was Kempe's error in his proof of the four colour theorem?

What I understand of his general idea is by the following case: Suppose an uncoloured "country" is surrounded by countries of four different colours Red (R), Blue (B), Green(G), Yellow(Y) with R,G and B,Y not sharing borders. Either there will be a contiguous chain of countries forming a red-green chain from R to G or not. If not, we can interchange the colours in the maximal such chain initiated from R to change the R colour to G. In this case we are done for now only three colours surround the uncoloured country. Otherwise due to planarity such a contiguous blue yellow chain will not exist from B to Y following which we are done again by a similar argument.

As far as I know this argument drops when five countries surround a given uncoloured country. Exactly how that happens is not clear to me.


The basic idea is that you can't simultaneously reduce the chains because they can interfere with each other. Specifically, if you have a R-Y chain and a R-G chain, then there can be an edge between the Y and the G which throws a wrench in the flipping and recoloring process, because the Y and the G both need to get turned into R, but they are adjacent.

There's a good discussion at here, and you can see a specific counterexample graph at that link as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.