← All problems

Seymour’s second-neighborhood conjecture

For every finite oriented graph G=(V,A), there exists a vertex v∈V such that ∣N2(v)∣≥∣N1(v)∣, where N1(v)={x∈V:(v,x)∈A} and N2(v)={x∈V∖N1(v):∃y∈N1(v) with (y,x)∈A}.\text{For every finite oriented graph }G=(V,A),\text{ there exists a vertex }v\in V\text{ such that }|N_2(v)|\ge |N_1(v)|,\text{ where }N_1(v)=\{x\in V:(v,x)\in A\}\text{ and }N_2(v)=\{x\in V\setminus N_1(v):\exists y\in N_1(v)\text{ with }(y,x)\in A\}.

References

Progress summary

Refreshed
Open · progress reported

Several restricted cases have advanced, but the general conjecture remains open; a stronger community-submitted result is conditional and unverified.

Proposed by Paul Seymour in 1990 and first published by Dean and Latka in 1995, the conjecture asserts that every finite oriented graph has a vertex with ∣N2(v)∣≥∣N1(v)∣|N_2(v)|\geq |N_1(v)|.

Known results

  • Tournaments: Fisher (1996); a short median-order proof was given by Havet and Thomassé (2000).
  • Minimum out-degree at most 66: Kaneko and Locke (2001).
  • Several regular, transitive, quasi-transitive, and Eulerian classes are settled.
  • A quantitative bound ∣N2(v)∣≥0.715538∣N1(v)∣|N_2(v)|\geq 0.715538|N_1(v)| is known, but does not reach the conjectured factor 11.

June–August 2026 restricted-case advances

Preprints claim the minimum-outdegree-77 case and the dense range n≤2δ+2n\leq 2\delta+2, raising possible-counterexample bounds; neither settles the unrestricted conjecture. A separate claimed general proof lacks independent mathematical assessment and is therefore omitted as a resolution.

Community submission (unverified)

Posted October 25, 2026: A submitted argument claims two Seymour vertices in every sink-free oriented graph, but explicitly uses the original one-vertex theorem as a premise; it is therefore not an independent proof of this conjecture.

Current status (as of October 2026): Several restricted cases are settled or claimed, but the unrestricted conjecture remains open, and the submitted two-vertex strengthening is unverified and conditional.

Sources

Solutions 1

Conditional strengthening: two distinct Seymour vertices in every nonempty finite sink-free oriented graph. The paper assumes the one-vertex Seymour theorem and a source pruning lemma, so this is related progress rather than an independent proof of the conjecture.See full solutionHide full solution

Conditional strengthening: two Seymour vertices in every sink-free oriented graph.

The paper Two Seymour vertices in every sink-free oriented graph deduces that every nonempty finite oriented graph without a sink has two distinct vertices v satisfying |N₂(v)| ≥ |N₁(v)|, where N₂ denotes vertices at directed distance exactly two. No extra degree, connectivity, order, or missing-edge restrictions are imposed.

The explicit premises are the ordinary one-vertex Seymour theorem and the finite-relation pruning lemma stated in the paper from the pinned OpenAI source. The deduction retains the exceptional boundary after deleting a hypothetical unique good vertex and aggregates gains in a transitive blowup to obtain the second vertex. The two-vertex conclusion is the cited Dara–Francis–Jacob–Narayanan strengthening.

Because the one-vertex assertion asked on this page is itself a premise, this entry is a conditional strengthening and related progress; it is not an independent proof of Seymour's original conjecture. The Lean support covers selected finite-cardinality, boundary and pruning consequences, not the full graph argument.

The full manuscript and supporting package are available on Zenodo, DOI 10.5281/zenodo.23430050.

Source and review status. The upstream inputs are stipulated at OpenAI/math revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. This is an AI-assisted manuscript with internal project reviews, not external peer review. The supporting Lean checks cover selected lemmas, not the full theorem.