There are two kinds of indirect proof: Proof by contrapositive and proof by contradiction.
Proof by contrapositive
It's sometimes easier to prove the contrapositive of an implication than it is to prove the implication itself. For example, suppose you want to prove
It's easier to prove
Why? Because if a number is not odd, then it's even, so it's a multiple of 2, say 2x. Its square, then, is 4x2, which is 2(2x2), a multiple of 2 and therefore even.
Proof by contradiction
Another kind of indirect proof is proof by contradiction. Proofs by contradiction have the form
not p implies q,That is, the negation of a claim p implies both a statement (q) and its negation (not q), so the claim p must be true.
not p implies not q,
For example, suppose you want to prove that in any graph, there are an even number of vertices with odd degree. Here's a sample proof:
Proof: Suppose that the conjecture is false. That is, suppose there exists some graph in which the number of vertices of odd degree is odd. What does that negation imply?
One thing we could do is sum up all of the degrees of all vertices in this graph. That sum would be the total of odd degrees and even degrees.
The sum of the odd degrees will be the sum of a list of odd numbers. That total will be odd because it is the sum of an odd number of odd numbers.
The sum of the even degrees will be even because the sum of any list of even numbers will be even. (Remember, 0 is an even number.)
Therefore the sum of all degrees of vertices in this graph is an odd number plus an even numberthat is, an odd number.
But there's another way of thinking about the sum of degrees of a graph's vertices. The degree of a vertex is the number of edges that end there. So adding up all the degrees of the vertices is a way of counting the number of ends of edges in the graph. But every edge has exactly two ends, so the total number of ends of edges has to be even.
Therefore the sum of degrees of vertices in this graph is both even and odd. That's a contradictiona contradiction following from the assumption that the graph has an odd number of vertices of odd degree.
Since the negation of the statement led to a contradiction, the statement must be true. The graph must have an even number of vertices of odd degree.
Copyright © 1999-2000 SciMathMN