Seymour’s second-neighborhood conjecture

The explanation

Draw four points, A, B, C and D. Draw an arrow from A to each of the other three. Then add a loop of arrows: B to C, C to D, and D back to B. Now count from each point. A reaches three points in one step. In two steps it reaches nothing new, because B, C and D were already counted. So A scores 3 against 0. B reaches only C in one step. It reaches D in two steps. B scores 1 against 1, and so do C and D.

The pattern in that drawing is the subject of Seymour's second-neighborhood conjecture. It is about oriented graphs. An oriented graph is a finite set of points joined by arrows. No arrow runs from a point to itself. Two points share at most one arrow, pointing one way. A point's first neighbors are the points one arrow away. Its second neighbors are the points exactly two arrows away. That count leaves out the starting point and its first neighbors. Each point is counted once, however many routes reach it. The conjecture says some point has at least as many second neighbors as first neighbors. In the drawing, A fails but B, C and D all succeed.

Leaving out points already reached is what gives the conjecture its biteSource 1. From A, the route A to B to C reaches C in two steps. But C is one step away already, so it does not count. A point with no outgoing arrows, called a sink, passes at once with 0 against 0. So the claim only has force when every point has arrows leaving it.

Nathaniel Dean and Brenda Latka recorded the conjecture in 1995. One special case gets the most attention: the tournament, which has an arrow between every pair of points. David Fisher proved that case in 1996. Frédéric Havet and Stéphan Thomassé gave a second proof in 2000. Later papers covered tournaments with a few arrows missing. Others added conditions on the points. Yoshihiro Kaneko and Stephen Locke handled graphs where the fewest outgoing arrows at any point is six or less. A computer-assisted preprint in 2026 handled seven.

Another approach settles for a weaker ratio. In 2003, Guantao Chen, Jian Shen and Raphael Yuster proved a weaker guarantee. Some point always has at least about 0.657298 second neighbors per first neighbor. In 2024, Hao Huang and Fei Peng raised this to about 0.715538. The conjecture asks for a ratio of 1.

This paper proves the full statementSource 2. It needs no condition on how the points connect or how many arrows they have. The proof runs by contradictionSource 3. It imagines a smallest graph where every point fails. Deleting arrows from that graph gives a rule for every group of points smaller than the whole graphSource 4. Its second step gains fewer new points than its first step. Then the paper replaces each point by a large tournamentSource 5. That turns the rule into a stronger, averaged form.

The obstacle is turning that growth rule into a contradiction. The paper tracks two collections of pairs of points and scores themSource 6. It then builds larger collections that should beat the best score. Those new collections can clash with each otherSource 7. Removing clashing pairs costs points from the score. The paper's new tool is a pruning bound that works for any finite relation between pointsSource 8. It charges part of the removal cost to points left uncovered afterwardsSource 9. With that accounting, the repaired score still beats the best one. That contradiction rules out the bad graph.

Back in the drawing, the theorem promised that some point scores at least even, and B does. It does not promise that every point does, and A shows why it cannot. The paper also draws consequences. One is about triangles of arrows. Suppose every point sends arrows to at least a third of all points. Suppose it also receives arrows from at least a third. Then, the paper claims, the graph contains a loop of three arrowsSource 10.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers every nonempty finite oriented graph, with second neighbors counted at distance exactly two. The paper's other consequences, such as the triangle result and the weighted forms, are not in the Lean scope note. No specialists have published a review yet.

What it doesn't show. This does not say that every point has this property, only that at least one point does.