This question is in part inspired by a quote I saw in an answer to another question:
The problem with incorrect proofs to correct statements is that it is hard to come up with a counterexample.
A little while ago, I attended a graph theory course in which there was a chapter on graph colourings. The most famous problem in this area is the four-colour theorem, which states that the vertices of any planar graph can be coloured using at most four colours in such a way that no two adjacent vertices have the same colour. This is easily shown to be equivalent to the more famous statement of the theorem concerning colourings of countries on a map. Our lecturer showed us the rather simple proofs of the six-colour and five-colour theorems (i.e., the four-colour theorem but with 'five' and 'six' substituted for 'four') and then showed us a slightly more complicated proof of the four-colour theorem.
At this point, whispers started going round the room. It is well known that the only known proof of the four-colour theorem, due to Appel and Haken, makes essential use of a computer to check thousands of cases and can certainly not be written down on a blackboard in under an hour. Our leccturer explained that the proof was incorrect, and left it to us as an exercise to find out why.
I worked at it a bit, and eventually found a problem with the proof. I looked online to find out if was right, but was unable to do so. However, I did see one thing that intrigued me. The proof that our lecturer had shown us was originally formulated by Alfred Kempe, and stood unchallenged for eleven years until Percy Heawood found the problem with it. What I found intriguing was the following:
Percy Heawood found a graph that was a counterexample to the proof!
So here's my question. Given that the four-colour theorem is correct, how is it possible to find a counterexample to an incorrect proof? My guess is what Kempe proved was slightly stronger than the four colour theorem, and the Heawood graph is a counterexample to that slight strengthening. But I'd be interested to find out if there's more that can be said.
I'd be especially interested if you have any other examples of counterexamples to incorrect proofs to correct statements.
Best Answer
Kempe's "proof" used induction on the number of vertices in the graph G. Given a graph with n vertices, he removed a vertex, colored the remaining graph in four colors using the inductive hypothesis, and then (and this is the hard part) re-inserted the missing vertex, which possibly resulted in having to "fix up" the coloring of its adjacent vertices - this is where the problem occurred.
The Heawood counterexample showed very clearly why the algorithm that Kempe used was invalid - when applied to Heawood's graph, it did not have the intended result. Thus it was this algorithmic portion of the proof that had a logical error that was exposed by the Heawood counterexample.
There are quite a few expositions of this entire affair; one chosen more or less at random is at http://web.stonehill.edu/compsci/LC/Four-Color/Four-color.htm