Seymour's second neighborhood conjecture

OpenAI's proof (2026) of Seymour's second neighborhood conjecture, that every finite oriented graph has a vertex with at least as many second as first out-neighbors; through minimal counterexamples, transitive tournament blow-ups, a pruning theorem proved with generic ranks, and an extremal argument; with weighted forms and consequences for directed triangles.

Four lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Second out-neighborhoods and minimal counterexamples
2. Blowing up by transitive tournaments
3. Ranks, matchings and pruning
4. The extremal argument and its consequences

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Finite graphs and directed graphs, finite-dimensional linear algebra (rank, kernels, determinants) and polynomials in several variables.