Extremal Principle

Consider the largest, smallest, first, last, or otherwise extreme object satisfying the condition.

A remarkably productive proof technique, because the extreme object has properties nothing else does — and those properties usually finish the argument.

The two standard shapes

1. Minimal counterexample

Assume the claim is false; take the smallest counterexample; derive a smaller one. Contradiction.

This is strong induction in disguise, and it is how most “every $X$ has property $P$” results are proved.

2. Extremal element in an optimal solution

Take an optimal solution and consider its extreme element (heaviest edge, longest path, last job). Show it can be exchanged or removed without loss — the basis of most exchange arguments and greedy proofs.

Worked examples

MST cycle property

The heaviest edge on any cycle is not in any MST (if strictly heaviest).

Proof. Suppose it were. Removing it splits the tree into two components; the cycle must cross that cut again at some lighter edge, and swapping gives a lighter spanning tree. ∎

Every tree has a leaf

Take the longest path in the tree. Its endpoint has degree 1 — otherwise the path could be extended, contradicting maximality.

This one-line argument proves that trees have $\ge 2$ leaves, and is the base case for most tree inductions.

Every DAG has a source

Take the longest path. Its start has in-degree 0 within the path, and any incoming edge would extend the path or create a cycle.

A graph with min degree $\ge 2$ contains a cycle

Take the longest path $v_0\dots v_k$. Since $\mathrm{deg}(v_k)\ge 2$, it has a neighbour other than $v_{k-1}$, which must be on the path (else the path extends) — giving a cycle.

$\sqrt{2}$ is irrational

Suppose $\sqrt{2}=p/q$ with $q$ minimal. Then $\frac{2q-p}{p-q}$ is another representation with a smaller denominator. Contradiction. (This avoids the usual parity argument entirely.)

Sylvester-Gallai

Given finitely many non-collinear points, some line passes through exactly two. Proof: take the smallest positive distance from a point to a line through two others; if that line had three points, a smaller distance would exist.

Where to look for the extreme

Setting	The extreme object
Graph	longest path, heaviest edge, min-degree vertex, largest component
Tree	a leaf, the deepest node, a centroid, an endpoint of the diameter
Sequence	maximum, minimum, first violation, longest increasing run
Set system	smallest set, an element in the most sets
Optimal solution	the last job, the heaviest item, the earliest deadline
Geometry	the leftmost point, the closest pair, the extreme point in a direction
Counterexample	the smallest one
Configuration	the one minimising a potential function

“Take the leftmost/lowest point” is the standard opening for geometry proofs and constructions — it is on the convex hull, and its extremality removes a case.

In constructive problems

Extremal reasoning suggests what to build:

• “Assign the largest value to the most constrained position” — a common greedy.
• “Start from the vertex of minimum degree” — often the forced first move.
• “Handle the extreme case first, then induct” — the standard construction shape.
• “The answer is achieved at an endpoint” — for linear objectives over an interval, always check both ends.

That last one is worth stating explicitly: a linear function on an interval is extremised at an endpoint, so when a parameter’s effect is monotone, only the boundary values need testing.

The related principles

Principle	Statement
Extremal	consider the extreme object
Pigeonhole	$n$ items in $m<n$ boxes ⟹ some box has two
Invariant	something is preserved ⟹ impossibility
Monovariant	something decreases ⟹ termination
Well-ordering	every non-empty set of positive integers has a least element
Induction	build up from a base case

Well-ordering is what makes “take the smallest counterexample” valid, and it is the same principle as induction viewed from the other side.

See also: Invariants · Proof Techniques · Exchange Arguments