A dense-case theorem for Seymour's second neighborhood conjecture

Jake Brukhman

Every oriented graph on n=2δ+2 vertices with minimum outdegree δ has a vertex whose exact second outneighborhood is at least as large as its first. With Fisher’s tournament theorem, this covers n≤2δ+2, without proving Seymour’s conjecture for all oriented graphs.

Sources for this record

What was already known

Fisher covered tournaments with n=2δ+1. Earlier dense-graph cases restricted the shape of missing edges; this result allows up to n/2 missing edges without such a restriction.

AI involvement AI-centered

GPT-5-family models found the fixed-target capacity and double-counting argument. The human author initiated, directed, edited and verified the final proof.

GPT-5-family models supplied the decisive dense-case argument under the author’s direction; stronger autonomy is not documented.

Importance Notable

The theorem adds a structurally unrestricted dense case and sharpens the lower bound on possible counterexample size.

Limitations

The n=2δ+3 case and the general conjecture remain open. A Claude audit covered an intermediate draft, while the author reports checking the final proof.

Technical verification Formal (human)

The author expressly reports verifying the proofs of the final dense-case theorem. This is a source-reported complete human proof check; the Claude audit of an intermediate draft is not counted as human or machine checking.

Formal checking

Author verification of final manuscript proofs

Checker
Paper author (sole human author)
Scope
Theorem 1.1 for n=2δ+2 and its corollary with Fisher’s theorem
Basis
Reported by the linked checker
Evidence source

Checking a formal statement does not establish that it matches the original problem.

Human understanding Few

The author’s check and editing do not separately document a human explanation of the fixed-target capacity mechanism. Few is the evidence default.

Correction and publication history

2026-10-18 · publication

The theorem adds a structurally unrestricted dense case and sharpens the lower bound on possible counterexample size.

Read this published revision