The Erdős-Hajnal conjecture for paths: does every path have the Erdős-Hajnal property?
A graph has the Erdős-Hajnal property if there is such that every -vertex graph with no induced subgraph isomorphic to contains a clique or a stable set of size at least . Erdős and Hajnal conjectured in 1977 that every graph has this property; the conjecture is open in general. This entry records the case of paths: does the path on vertices have the Erdős-Hajnal property for every ? Before this work it was known for ( by Nguyen, Scott and Seymour, 2023), and for all only with the weaker bound in place of .
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Graph theory; induced subgraphs, Erdős-Hajnal conjecture
- Posed by
- Paul Erdős and András Hajnal (the general conjecture; paths are its special case)
- Year posed
- 1977
- Years open
- 49y
- Solved
- 2026-10-17
- Model
- ChatGPT-6 Astra
- Vendor
- OpenAI
- Collaborators
- Tung H. Nguyen
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 42 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1 of arXiv:2610.24887 (Tung H. Nguyen, v1 17 October 2026): has the Erdős-Hajnal property for every . Theorem 1.2 extends it to the trees and the graphs , which include the bull, E and the bird. This is not the general conjecture. Concurrent independent proofs of the path case: Yuwen Zhou's repository (public 8 October 2026, with a Lean development conditional on stated literature hypotheses and an anonymous project), later arXiv:2611.01963 (Huang, Zhou, Zhou; Claude Opus 5.5 and ChatGPT-6), and Google DeepMind's Cogentic manuscript with Lean (18 October). The first public proof of the path case may not be this one.
What the AI did
From the paper's Declaration of generative AI use: ChatGPT-6 Astra was mathematically involved in two subsections and one section; the ideas in the rest are the author's. Asked to prove a weaker version of a modular-decomposition lemma, Astra proved the full purity version; after discussions directed by the author it found the proof of the path-splitting lemma for , which the author extended to general ; it also cleaned up the author's endpoint-switching argument. Astra assisted with proofreading and mathematical review; ChatGPT-6 Luna helped copy-edit and ChatGPT-6 Sol drew the figures.
Verification
No independent mathematician has checked this yet. Read by this site on 15 November 2026 in the TeX source of arXiv:2610.24887v2: the conjecture and Theorem 1.1 as stated in the introduction, the concurrent-work section and the AI declaration. The proof (39 pages) was not refereed here and there is no formal proof of this paper. Checked against the concurrent work: Zhou's GitHub repository was created 8 October 2026 (UTC), Nguyen's v1 posted 17 October, DeepMind's manuscript committed 18 October; DeepMind's README credits Nguyen as first to their knowledge. The catalog had no entry on this question.
Sources
- PaperarXiv
- CodeZhou's repository: manuscript and Lean development (public 8 Oct 2026, Zenodo 23270286)
- Independent workHuang, Zhou and Zhou, The Erdős-Hajnal property for paths (arXiv, 1 Nov 2026), concurrent proof first public 8 OctGoogle DeepMind, Erdős-Hajnal for paths and beyond (Cogentic, Gemini 4 Argon), with Lean
- Problem recordNguyen, Scott and Seymour, Induced subgraph density VII: the five-vertex path
- OtherAnonymous AI-generated proof for P6 with Lean (27 Sep 2026)
Submitted by MellowGander562 on