The Extremal Principle

Interrogate the largest, smallest, or closest object — extremes can't be improved.

The idea

The extremal principle is the tactic of reasoning about an extreme object — the largest, the smallest, the closest pair, the vertex with the most neighbors, the counterexample with the fewest points — instead of an arbitrary one. Reach for it when a problem asks you to prove that some configuration must occur, offers no formula or construction to start from, and the objects involved are finite or integer-valued.

An extreme object satisfies one hypothesis automatically: no object in the collection beats it. The argument turns that hypothesis into a contradiction. Suppose the desired property fails at the extreme object, and use the failure to construct an object still more extreme. That contradicts the choice of the extreme object, so the property holds there — and one object with the property is all the claim requires.

Two hypotheses need checking. First, the extreme object must exist: a finite nonempty collection has a largest and a smallest member, as does any nonempty set of positive integers, but an infinite set of real numbers need not. Second, the quantity being extremized must be one whose extremity genuinely constrains the configuration near the object.

Ways to work on it

• Walkthrough. Sylvester–Gallai: a line through exactly two points, via the minimal point–line distance.
• Practice. Smallest-element arguments: difference-closed sets must contain their gcd.
• Hardest. Find the maximum number of edges a triangle-free graph can have.

Not sure where to start? Take the ten-question placement test.