Seymour’s second-neighborhood conjecture

Draw arrows around a four-dot loop $A\to B\to C\to D\to A$, then add the shortcut $A\to C$. From A, one step reaches B and C. Two steps reach C and D, but C was already a direct destination, so only D is new: one new destination versus two direct ones.

From B, one step reaches C and two steps newly reach D, so the counts are equal. Seymour asks whether at least one dot always has as many new two-step destinations as direct destinations in every finite nonempty graph of one-way arrows. Self-links, repeated arrows and opposite arrows between the same pair are excluded.[1] [2]

In a finite nonempty network of one-way arrows, must some vertex reach at least as many new vertices after two steps as it reaches directly? Seymour's conjecture concerns oriented simple graphs: no loops, repeated edges or opposite arrows. Count destinations, not paths, and remove the starting vertex and direct destinations from the two-step set.

Write $N^{+}(v)$ for the direct out-neighbors and $N^{++}(v)$ for the second out-neighbors, those at directed distance exactly two. The proposed local witness satisfies $$|N^{++}(v)|\geq|N^{+}(v)|.$$ For the cycle $A\to B\to C\to D\to A$ plus $A\to C$, the sets for A are $N^{+}(A)=\{B,C\}$ and $N^{++}(A)=\{D\}$. For B they are $\{C\}$ and $\{D\}$, respectively. One graph can therefore contain vertices that fail and others that pass the comparison.

A stronger matching condition asks to pair every direct out-neighbor with a distinct second out-neighbor using an arrow between them. Equal or larger set sizes alone do not guarantee those particular pairings: which arrows exist also matters.[1] [2]

This is unknown for arbitrary finite graphs without two-way edges.[2]

The June 2026 preprint reports a partly computer-assisted result for graphs of minimum out-degree at most seven, rather than arbitrary oriented graphs. The July paper proves the stronger matching property in specified classes. Its revised version also gives a counterexample to the universal matching condition; this does not disprove the original neighborhood-count conjecture.[1] [2]

Extra routes can merge at the same destination, and a shortcut can turn a new two-step destination into an old direct one. The count therefore measures genuine local branching, rather than the number of paths. Understanding that branching helps describe structure that an arbitrary one-way network must contain.[1] [2]

Neighborhood size and the ability to make distinct assignments are different kinds of information. The stronger matching formulation links this problem to the theory of selecting disjoint pairings between two sets. Its failure in general explains why a convenient pairing argument cannot simply replace the original counting target.

The original conjecture would still impose a structural constraint on every oriented graph: merged paths and shortcuts cannot suppress the new-destination count at every vertex simultaneously. That is an intrinsic question about directed expansion, without assuming a regular, random or otherwise specially organized graph.[1] [2]