Counterexamples to proofs of correct statements

Solution 1:

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

Solution 2:

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.

Solution 3:

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)