Math Conjectures

Seymour's Second Neighborhood Conjecture

OPENMajorConjectureProposed c. 1990 · Standard version

Canonical statement

Let DD be a finite oriented graph (no loops and no pair of oppositely directed edges). For v∈V(D)v\in V(D), let N+(v)N^+(v) be its out-neighborhood and let N++(v)N^{++}(v) be the set of vertices whose directed distance from vv is exactly 22. Then some vertex vv satisfies
∣N++(v)∣≥∣N+(v)∣. |N^{++}(v)|\geq|N^+(v)|.
View source LaTeX
Let \(D\) be a finite oriented graph (no loops and no pair
of oppositely directed edges). For \(v\in V(D)\), let
\(N^+(v)\) be its out-neighborhood and let \(N^{++}(v)\) be the set of
vertices whose directed distance from \(v\) is exactly \(2\). Then some
vertex \(v\) satisfies
\[
  |N^{++}(v)|\geq|N^+(v)|.
\]
GRAPH-020:[Fisher1996SecondNeighborhood][Sullivan2006SecondNeighborhood][BaiLiPark2026SecondNeighborhood]
Graph theoryCombinatorics

Notes

An oriented graph is a directed graph with no loops and no pair of oppositely directed edges. Seymour's second neighborhood conjecture, whose modern formulation emerged around 1990, asserts that every finite oriented graph contains a vertex vv with at least as many second out-neighbors as first: ∣N++(v)∣≥∣N+(v)∣|N^{++}(v)|\ge|N^+(v)|, where N++(v)N^{++}(v) is the set of vertices at directed distance exactly two from vv. Informally, some vertex's sphere of influence does not shrink when one passes from radius one to radius two.

The most celebrated special case is that of tournaments, where Fisher proved the statement, confirming what had been posed as Dean's conjecture [Fisher1996SecondNeighborhood]. The problem sits close to the Caccetta–Häggkvist circle of questions on out-degrees and directed girth, a connection surveyed by Sullivan [Sullivan2006SecondNeighborhood]. Beyond tournaments the conjecture has been verified for a number of structured classes of oriented graphs, and strengthened forms are actively investigated [BaiLiPark2026SecondNeighborhood].

For arbitrary oriented graphs the conjecture remains open; a resolution must either produce a vertex with the required second-neighborhood expansion in every orientation or exhibit a counterexample.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.