Proof by Exhaustion

Sometimes a question has only a handful of possibilities — the few teams left in a knockout round, the ways four friends can sit in a row, the settings on a simple lock. When the list is short enough to write out, you can settle the matter for certain by simply trying every case. Computers love this: the famous four-colour map theorem was finally proved by a machine grinding through every case.

Proof by deduction warned you that checking examples isn't a proof, because there are usually infinitely many cases. But what if there aren't? What if a claim has only a small, finite number of possibilities?

Then you can do the most honest thing imaginable: check every single one. Line up all the cases, verify the statement in each, and — since there is nothing left to test — you have proved it. This brute-force but perfectly valid method is called proof by exhaustion: you literally exhaust the cases.

Suppose we claim that every integer from 1 to 5, when squared, is less than 30. There are only five cases, so we just check them all:

1^2 = 1,\quad 2^2 = 4,\quad 3^2 = 9,\quad 4^2 = 16,\quad 5^2 = 25

Every result is below 30, and there are no other cases to try, so the statement is proved. ✓

The one danger: are the cases really finite and complete?

Exhaustion lives or dies on two questions. First, is the list of cases finite — can you actually get to the end? Second, do the cases cover every possibility, with no gaps? Miss one case, or leave the door open to infinitely many, and the "proof" proves nothing.

To prove a statement by exhaustion:

break the problem into a finite set of cases that together cover every possibility;
verify each case on its own;
if all cases pass, the statement is proved;
if even one case fails, the statement is false;
it is only usable when the cases are finite — you can't exhaust infinitely many.

Worked example 1 — a clever trick that makes infinity finite

Claim: the square of any whole number ends in one of the digits 0, 1, 4, 5, 6, 9.

There are infinitely many whole numbers — so surely exhaustion is hopeless? Here is the insight: the final digit of n^2 depends only on the final digit of n. So there are really only ten cases to check — the last digit being 0 through 9:

0^2{=}0,\ 1^2{=}1,\ 2^2{=}4,\ 3^2{=}9,\ 4^2{=}16,\ 5^2{=}25,\ 6^2{=}36,\ 7^2{=}49,\ 8^2{=}64,\ 9^2{=}81

Reading off the units digits: 0, 1, 4, 9, 6, 5, 6, 9, 4, 1 — always one of \{0, 1, 4, 5, 6, 9\}. Ten cases exhaust an infinity of numbers, so the claim is proved. (This is why no perfect square ever ends in a 2, 3, 7 or 8 — a genuinely useful fact you just proved by brute force.)

Worked example 2 — the two-case "odd or even" split

The most common exhaustion proof at A-level has just two cases: every integer is either even or odd, so proving both settles it for all integers.

Claim: n^2 + n is even for every integer n.

Case 1 — n is even, say n = 2k:

n^2 + n = n(n + 1) = 2k(2k + 1) = 2\big[k(2k+1)\big] \ \Rightarrow\ \text{even.}

Case 2 — n is odd, say n = 2k + 1:

n^2 + n = n(n + 1) = (2k+1)(2k+2) = 2\big[(2k+1)(k+1)\big] \ \Rightarrow\ \text{even.}

Every integer is even or odd — those two cases leave no gaps — and the claim holds in both. So it is proved for all integers. (Neat shortcut: n(n+1) is a product of two consecutive integers, one of which must be even — but splitting into cases is the exhaustion route.)

Worked example 3 — every single-digit number

Claim: no single-digit whole number (0 to 9) is equal to its own square, except 0 and 1.

Only ten values are possible, so check them: 0^2{=}0 ✓, 1^2{=}1 ✓, then 2^2{=}4 \ne 2, 3^2{=}9 \ne 3, and every larger one only grows further away. All ten cases confirm the claim, and there are no others, so it is proved. Nothing subtle — just complete.

Exhaustion means every case, not "several convincing ones". Two ways to wreck the proof:

An infinite claim. You cannot "exhaust" a statement about all integers by checking a handful — that's just examples wearing a disguise. The cases themselves must be finite (or cleverly reduced to finite, like the "last digit" trick above).
A missing case. If your cases don't cover every possibility, one untested case could be the counterexample that breaks everything. Splitting into "even and odd" works because those two truly cover all integers; splitting into "even and prime" would leave a gaping hole (what about odd non-primes like 9?). A gap doesn't weaken the proof — it destroys it.

The rule of thumb: before you write a single case, ask "does my list of cases, taken together, catch literally everything?" If not, stop.

Proof by exhaustion powered one of the most famous — and most controversial — proofs in history. The Four Colour Theorem says any map can be coloured with just four colours so that no two neighbouring regions share a colour. Mathematicians chased it for over a century.

In 1976, Kenneth Appel and Wolfgang Haken finally cracked it — by reducing the infinite variety of maps down to about 2000 special cases, then setting a computer loose to check every one. It was the first major theorem proved by machine. And it sparked a genuine philosophical storm: no human could ever verify all those cases by hand, so is it really a "proof"? If you can't follow every step yourself, do you truly know it's true? That question is very much alive today, in the age of computer-assisted and AI-driven mathematics.