The Extremal Principle in Graphs
Take the longest path, the vertex of largest degree.
Pick the extreme object (the longest edge, the smallest counterexample, the point closest to a line) and derive a contradiction or a forced structure. Because the extreme exists (finiteness or well-ordering guarantees it), the argument is airtight.
In combinatorics it drives most 'show some configuration must occur' proofs: take a vertex of maximum degree, a longest path, a triangle of least area.
Zeitz calls this one of the handful of genuinely universal problem-solving moves, and it pairs naturally with infinite descent.
Guides on The Extremal Principle in Graphs
- Ramsey problems for beginners: one move, four levelsRamsey olympiad problems in order of difficulty, from six people to three colours and number puzzles. One vertex, pigeonhole its edges, then look inside.
- Extremal graph problems for beginners: the bound and the exampleAn extremal graph problem is two problems: a bound nobody can beat and an example that reaches it. How to spot one, and which vertex to pick first.
- The extremal principle: how to choose which extreme to takeTaking the largest or the smallest is the easy half. The three signals that call for an extreme, and the one question that tells you if you picked the right one.
Train it on Lemma
The Extremal Principle in Graphs unlocks at Level 6 of Lemma's eight-level ladder, with lessons that teach it and drills that make it stick. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your levelMore techniques
- Infinite Descent & Vieta JumpingNo smallest counterexample can survive.
- The Incircle ConfigurationTangent lengths turn sides into s − a.
- All 29 techniques →