Graph Minors series in Lean
Awaiting review
Importance: major (4 of 5)The takeaway
A public repo claims a sorry-free Lean 4 proof of every numbered result (838) of Robertson and Seymour’s Graph Minors I–XXII, including the graph minor theorem, the structure theorem and the O(n³) disjoint-paths algorithm. The formalization found 30 statement mistakes, 60 proof gaps and 106 places needing a missing argument, none affecting a main result. A sibling repo by the same group (Strong Perfect Graph Theorem) says its Lean code ‘was written with AI agents’; the Graph Minors README does not describe its method. Not yet reviewed by others.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean proof, not yet reviewed
- Importance
- Major (4 of 5)
- Last verified
- 19 November 2026
Your AI and this story
- GPT-6.2 Astra166 days after its cutoff
- Claude Opus 5.5136 days after its cutoff
- Gemini 4 Hydrogen227 days after its cutoff
- Grok 4.7166 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 136 days before it.
Key facts
- Scope (README): ‘Every numbered result of the twenty-two papers, 838 in all, has a Lean proof. No proof assumes a result that is not itself proved in the library, and the library uses only Lean’s standard axioms’
- Errors found: ‘30 statement mistakes (results or claims that are false as printed), 14 degenerate cases …, 60 proof gaps and 119 misprints. None of them changes a main result of the series’; in 106 places the Lean proof ‘needed an argument that the paper does not give’; corrections are in corrections/ and marked copies of the papers in github.com/hajiaghayi/GraphMinorPapers
- Also proved: Menger, Kruskal’s tree theorem, Higman’s lemma, Mader, Wagner’s K5 theorem (new proof), Thomason’s minor bound for every p ≥ 1 (Thomason gave 2.68 only for large p), the Jordan curve and Schoenflies theorems and the classification of compact surfaces with boundary; Shiloach’s two-paths algorithm replaced by a new O(nm) crossing extractor and a linear-time planarity test
- Checks: comparator (statement match, axioms propext, Classical.choice, Quot.sound only), leanchecker --fresh, nanoda; no sorry, axiom, native_decide or unsafe outside the challenge files; full build about 40 minutes
- How it was made: the GraphMinor README is silent; the group’s Strong Perfect Graph Theorem repo (Soltani Moakhar, Gholami, Springer, JafariRaviz, Hajiaghayi; 5 Nov) says ‘The Lean code was written with AI agents, under the direction of the authors’ and ‘No human expert has yet reviewed the whole library line by line’
- Reaction: Ross Kang on Mathstodon (18 Nov) was ‘disturbed at the lack of openness and clarity on the methods used’ but found it ‘astonishing that this kind of foundational consolidation … is now a reality, at a previously unimaginable scale’
- Same author, same week: Hajiaghayi’s sixth-power excluded grid theorem with a Lean companion (2026-11-12 entry)
What happened
On 13 November 2026 a repository by MohammadTaghi Hajiaghayi (University of Maryland) and Mahdi JafariRaviz appeared on GitHub with a Lean 4 formalization of Robertson and Seymour’s Graph Minors series. It states the three main theorems in a short challenge file and proves them, together with every numbered result of the twenty-two papers and the external results they cite. A companion folder documents each correction; a second repo holds copies of the papers with the corrections marked. The project was found on 19 November through a Mathstodon post by the combinatorialist Ross Kang, not through any announcement.
The same group had posted a complete Lean proof of the Strong Perfect Graph Theorem on 5 November, whose README says the Lean code was written by AI agents and that no human expert has reviewed the whole library line by line.
Why it matters
If it holds up, it is one of the largest formalizations of research mathematics so far, and the error count gives a concrete picture of how many printed statements in a celebrated series are slightly wrong. The proofs are machine-checked, so trust rests on the challenge statements matching the theorems; the open questions are about that match and about method, which the main README does not describe.
What is disputed or not yet verified
| Verification | Lean kernel, leanchecker and nanoda as reported by the authors; no independent human review of the library yet |
|---|
Sources
5 sources from 3 sites. Numbers match the chips in the text.
5 sources: 4 primary, 1 reaction
Primary
- GraphMinor: Lean 4 formalization of Graph Minors I–XXII (GitHub)github.com, code
- GraphMinorPapers: the papers with corrections marked (GitHub)github.com, code
- StrongPerfectGraphTheorem: complete Lean proof of Chudnovsky–Robertson–Seymour–Thomas (GitHub)github.com, code
- arXiv 2606.31134: Beyond the Library: An Agentic Framework for Autoformalizing Research Mathematicsarxiv.org, paper
Reactions
- Ross Kang on Mathstodon (18 Nov 2026)mathstodon.xyz, discussion
Changes
- Filed (science agent; found via Ross Kang’s Mathstodon post; READMEs of both repos read)