Kempe's proof of the four colour theorem

2.7k Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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.