# Counterexamples to proofs of correct statements

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.

-
You might enjoy Proofs and Refutations by Imre Lakatos. – joriki Mar 24 '12 at 13:38
I guess it means counterexample to the (unjustified part of the) "proof", not counterexample to the theorem. – FiniteA Mar 24 '12 at 13:46
Appel and Haken's is not the only known proof of the four-colour theorem. There is a simpler proof by Robertson, Sanders, Seymour, and Thomas. – lhf Mar 24 '12 at 16:23
Since I was the one who quoted Lenstra saying this: as I understood the quote, the problem is that, when confronted with an incorrect proof of a statement, one usually looks for a counterexample to the statement. In fact, that is, usually, the best way to confront the person proposing the argument: if the statement that you pretend to prove is false, then the game is over. The problem with incorrect statements to correct proofs is that you must find a specific step in the proof that is invalid, and find a counterexample to that step. (cont) – Arturo Magidin Mar 24 '12 at 21:06
(cont) But sometimes the problem is that there is an unwarranted implication; constructing a counterexample may be difficult because in the context of the result it may very well be true because the consequent is true. So you need to find a "parallel" situation in which the premises hold but the conclusion does not. In which case, the person proposing the argument may very well say "But that's not the situation we are in..." Of course, sometimes it is perfectly possible to find a 'counterexample' as you describe: a specific example in which the proposed argument does not hold. – Arturo Magidin Mar 24 '12 at 21:08

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

-

Usually proofs have many steps, and establish auxiliary results on the way to the final goal. A counterexample to an auxiliary result would unambiguously dsqualify the proof, without disproving the ultimate statement to be proved.

-

I don't know enough graph theory to come up with an example there. So let me get an example from calculus.

True assertion: let $f$ be continuous on $[a,b]$, $F(x)=\int_0^xf(t)dt$. Then $F'(x)=f(x)$.

"Proof": we have $$F(x+h)-F(x)=\int_x^{x+h}f(t)dt,$$ so $$\tag{1} f(x)\leq\frac{F(x+h)-F(x)}h\leq f(x+h).$$ As $f$ is continuous, $f(x+h)\to f(x)$, so $$F'(x)=\lim_{h\to0}\frac{F(x+h)-F(x)}h=f(x).$$

This proof is wrong because the inequality (1) doesn't necessarily hold when $f$ is not increasing. As a counterexample to that inequality, let $f(x)=-x$.

(of course this proof can be repaired to become an actual proof of the theorem, but the point is that it contains a false assertion, and a counterexample to this false assertion can be provided)

-