Seymour's Second Neighborhood Conjecture
Seymour conjectured that every oriented graph has a vertex with . It holds for oriented graphs of minimum out-degree exactly , the first improvement to the out-degree threshold since Kaneko and Locke settled degree in 2001.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Computation
- Field
- Graph theory
- Posed by
- Paul Seymour
- Year posed
- 1990
- Years open
- 36y
- Solved
- 2026-06-29
- Model
- ChatGPT 5.5 Pro
- Vendor
- OpenAI
- Collaborators
- Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
minimum out-degree 7; the conjecture is open in general
What the AI did
The CP-SAT models behind the computational part were developed with assistance from ChatGPT 5.5 Pro; the resulting OR-Tools encodings were then run and independently checked by the authors.
Verification
The proof leans on a CP-SAT computation whose encodings the authors state they verified independently. arXiv preprint, not peer-reviewed.