UMBC CMSC203, Discrete Structures, Spring 2009

Proofs by Contradiction

A proof by contradiction is similar to an indirect proof. However, indirect proofs are used with implications, whereas, a proof by contradiction can be used in a more general setting.

Claim: There are an infinite number of prime numbers.

Proof: Suppose not. Then, there is a finite number of prime numbers and we can let p₁, p₂, ..., p_n be all the prime numbers. We define

Q = p₁ p₂ ... p_n + 1.

If Q is prime, then Q is a prime number not on the list p₁, p₂, ..., p_n because Q is larger than every p_i. That contradicts the assumption that p₁, ..., p_n contain all of the prime numbers.

On the other hand, suppose that Q is composite. Let q be a prime factor of Q. Note that Q is not divisible by any of the p_i. Why? because the product p₁ p₂ ... p_n is a multiple of p_i and the next multiple of p_i is p₁ p₂ ... p_n + p_i. Since

p₁ p₂ ... p_n  <  Q  <  p₁ p₂ ... p_n + p_i,

Q cannot be a multiple of p_i. That means the prime factor q of Q does not appear on the list of prime numbers p₁, p₂, ... p_n since Q is a multiple of q. Thus, we also have a contradiction in this case.

In either case, we found a prime number not on the list of prime numbers. Thus, we can conclude that our premise that there is a finite number of prime numbers must be false. Thus, there must be an infinite number of primes.

QED

Claim: The graph below is not 3-colorable.

Proof: Suppose by contradiction that the graph is 3-colorable using 3 colors we'll call red, green and blue. Then, every vertex in the graph is colored red, green or blue. Without loss of generality, let the color of vertex a be red. Vertices b and d must be colored different colors that are not red. Let these two colors be, respectively, blue and green. Now, vertex e is adjacent to vertices a and d, so it cannot be colored red or green. Thus, vertex e must be colored blue. Similarly, c must be green, g must be red and we arrive at the following partial coloring:

Note that vertex f is adjacent to vertices b, d and g, which are, respectively, blue, green and red. Thus, vertex f cannot be colored blue, green or red. This contradicts our previous conclusion that every vertex is colored red, green or blue. Thus, our initial assumption that the graph is 3-colorable must be false.

QED

Claim: √2 is an irrational number.

Proof: Suppose not. Then we can express √2 as a ratio of two integers n and m such that the greatest common divisor of n and m is 1 (i.e., gcd(n,m) = 1). [This argument relies on the fact we learned in elementary school about reducing fractions to lowest terms.] Thus, we have

√2 = n/m.

Squaring both sides gives us:

2 = n²/m²
2 m² = n².

Thus, n² is an even number. So, n itself must also be an even number. (If n were odd, n² would also be odd.) Therefore, n = 2k for some integer k and we have

2 m² = n²
2 m² = (2 k)²
2 m² = 4 k²
m² = 2 k².

So, m² is also even, which in turn implies that m is even. Therefore, both n and m are divisible by 2. This contradicts our assumption that gcd(n,m) = 1. Thus, our initial assumption that √2 is rational must be false.

QED