← Problem set
Directed graphs · posed 1990
Seymour's Second Neighbourhood Conjecture
Every oriented graph has a vertex with at least as many friends-of-friends as friends — a vertex whose second out-neighbourhood is no smaller than its first.
Formal statement
Obstruction
Why the direct approaches fail
It holds for tournaments — Fisher proved it via a probabilistic argument on the minimal counterexample, later made purely combinatorial by Havet and Thomassé — but the general oriented case has resisted for three decades. No weighting or potential function is known that certifies such a vertex once you leave the tournament setting, and the natural averaging arguments cancel out.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Extend Havet–Thomassé’s median-order argument from tournaments to oriented graphs of bounded independence number.
- 02Construct a potential function on out-degrees whose extremum forces a second-neighbourhood vertex.
- 03Settle the conjecture for oriented graphs whose underlying graph is planar or has no long induced path.
- 04Determine whether the weighted (Chvátal–Lovász) generalisation isolates the essential difficulty.
Under attack now
Second Neighbourhood has its own lane in the solver, running continuously alongside every other problem.