A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7
2026-06-29 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors proved a math puzzle called Seymour's second neighborhood conjecture for special directed graphs where each point has at least 7 arrows going out. This is the first time in about 20 years that someone improved the known cases, since a previous result for points with 6 arrows going out. Their proof uses some computer help to check many small possible counterexamples after simplifying the problem. The computer tools ensured no exceptions could exist in the reduced cases.
Seymour's second neighborhood conjectureoriented graphsminimum out-degreedirected graphslocal reductionscomputer-assisted proofCP-SATOR-Toolsinfeasibility checksgraph theory
Authors
Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen
Abstract
We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to $7$. This gives, to our knowledge, the first improvement of the minimum out-degree threshold in two decades, since the work of Kaneko and Locke in 2001, who resolved the conjecture for oriented graphs whose minimum out-degree is at most $6$. The proof is partially computer-assisted: after a sequence of local reductions, the remaining finite obstruction models are eliminated by reproducible OR-Tools CP-SAT infeasibility checks.