Seymour’s second-neighborhood conjecture

Proposed by Paul Seymour in 1990 and first published by Nathaniel Dean and Brenda J. Latka in 1995, the conjecture asserts that every finite oriented graph has a vertex whose second out-neighborhood is at least as large as its first. The tournament case is known as Dean's conjecture.

Known results

• Fisher (1996) proved the tournament case; Havet and Thomassé (2000) gave a short median-order proof.
• Kaneko and Locke (2001) proved the conjecture when the minimum out-degree is at most $6$.
• Lladó (2013) proved it for regular oriented graphs with out-degree $r$ and connectivity $r-1$.
• Cary (2019) proved it for certain Eulerian oriented graphs.

June–August 2026 claimed extensions

A June preprint claims the minimum-outdegree-$7$ case, which would force any counterexample to have minimum out-degree at least $8$ and at least $19$ vertices. An August manuscript claims the dense case $n\leq 2\delta+2$, implying a lower bound of $17$ vertices unconditionally; it credits GPT-5 family models with the exploration and proof development. Neither claim resolves the unrestricted conjecture.

Current status (as of August 2026): The tournament and several restricted cases are settled, while the dense-case and minimum-outdegree-$7$ extensions remain claimed results and the unrestricted conjecture is open.