MATtours of discrete mathematics

Proof by contradiction

A proof by contradiction is based on the idea that if an assumption leads to an absurdity or to something that could not possibly be true, then the assumption must be false.

Proofs that rely on this technique are sometimes referred to as indirect proofs or reductio ad absurdum.

If you have a conjecture that you are trying to prove, you attempt a proof by contradiction by saying to yourself, "Well, let's assume that the conjecture is false. What would that imply?"

Here is an example of a proof by contradiction:

Conjecture: In any graph, there are always an even number of vertices with odd degree.
Proof: Assume that the conjecture is false. Then there would exist some graph in which the number of vertices of odd degree was odd. What else could we say about such a graph?
One thing we could do is sum up all of the degrees of the vertices in this graph and see if that number was odd or even. We can do this without exactly adding if we let m represent the sum of all the odd degrees and let n represent the sum of all the even degrees and then ask ourselves whether m + n will be odd or even.
The sum of the odd degrees will be the sum of a list of odd numbers. This list will have an odd number of numbers in it, because we are thinking about a graph which has an odd number of vertices with odd degree. So the number m will be odd because it is the sum of an odd number of odd numbers.
The sum of the even degrees (which we are representing by n) will be 0 if there are no vertices of even degree. Otherwise it will be even because the sum of any list of even numbers will be even.
If n = 0, m + n will be odd because m is odd. Otherwise, m + n will be the sum of an even number and an odd number, and this number will also be odd.

So at this point we know that if a graph exists which has an odd number of vertices with odd degree, the sum of all the degrees of all the vertices in that graph will be odd.

Now wait a minute! Here comes the absurdity. . . .

Can you really have a graph where the sum of all the degrees of the vertices is odd?

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.

So our assumption that a graph with an odd number of odd-degree vertices exists, leads to a situation that is impossible, so no graph could possibly exists.

Therefore a graph will always have an even number of vertices of odd degree.