Another proof technique relies on the assumption that a statement \(Q\) cannot be both true and false. The technique we describe in this section is an example of indirect proof known as proof by contradiction.
To prove the statement \(P\Rightarrow Q\) by contradiction, we assume \(P\) and \(\neg Q\) (which places us in row 2 of Table 1.2.14), and thus that \(P\Rightarrow Q\) is false. We proceed deductively until we contradict some assumption or known fact. Thus, our original assumption of \(\neg Q\) is false, which means \(Q\) and thus \(P\Rightarrow Q\) are both true.
Suppose ten ducks are paddling in four ponds, but no pond contains at least three paddling ducks. This means that each of the four ponds contains at most two ducks.
Aside
That is, the first pond contains at most two ducks, the second pond contains at most two ducks, the third pond contains at most two ducks, and the fourth pond contains at most two ducks, for a total of (at most!) \(2+2+2+2 = 8\) ducks. This contradicts the given assumption that ten ducks are paddling in four ponds. Thus, there must be a pond with at least three ducks.
Let’s consider a different example now, where a direct proof would be extremely difficult (or impossible). Theorem 3.2.2, which was known to the Pythagoreans, states that \(\sqrt{2}\) is irrational, i.e., that there are no integers \(p\) and \(q\ne 0\) such that \(\sqrt{2} = \frac{p}{q}\text{.}\)
Suppose that \(\sqrt{2}\) is rational, i.e., there exist integers \(p, q\) with \(q\ne 0\) such that \(p,q\) have no common factors (i.e,. \(p/q\) is in “lowest terms”) and \(\sqrt{2} = p/q\text{.}\)
Begin by squaring both sides to obtain \(2 = \frac{p^2}{q^2}\text{,}\) which we may rewrite as \(2q^2 = p^2\text{.}\) Since \(q^2\) is an integer, this means that \(p^2\) is even. We may conclude (with a nod to Theorem 3.1.3 and Theorem 3.1.5) that \(p\) is even, and write \(p = 2k\) for some \(k\in\Z\text{.}\) We thus obtain
and canceling a 2 from each side yields \(q^2 = 2k^2\text{.}\) By an argument similar to the above, \(q\) is even. But here arises a contradiction, as we assumed \(p\) and \(q\) have no common factors, yet we have proved they are both divisible by 2.
Suppose \(m\) is even but, for a contradiction, that \(m^2\) is odd. Then there exist integers \(j,k\) such that \(m = 2j\) and \(m^2 = 2k+1\text{.}\) We observe that \(m^2 = m\cdot m = (2j) \cdot (2j) = 2(2j^2) = 2k+1\text{.}\) Thus, \(m^2\) is both even and odd, in clear violation of Axiom 3.1.9. We therefore find that \(m^2\) cannot be odd, and must be even.
For example, the degree sequence of the graph in Figure 2.1.2 is \((2,2,1,1)\text{,}\) while the degree sequence of the graph in Figure 2.1.3 is \((2,2,2,0)\text{.}\)
