Investigation strategies

Indirect proof

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

If the square of a number is odd, then the number is odd.

It's easier to prove

If a number is not odd, then its square is not odd.

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 4x², which is 2(2x²), 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,
not p implies not q,
Therefore p,

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.

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 number—that 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 contradiction—a 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.