Murty–Simon conjecture: proof for all n, bound found by GPT-5.6 Sol
Event confirmedAwaiting review
Importance: major (4 of 5)The takeaway
The Murty–Simon conjecture (Plesník 1975, Murty and Simon) says a diameter-2-critical graph on n vertices has at most ⌊n²/4⌋ edges, with equality only for the balanced complete bipartite graph. Füredi proved it in 1992 only for n above a tower of 2s of height about 10¹⁴. On 28 Oct Sanjana Das and Jacob Fox (Stanford) posted a proof for every n. Their AI statement says the proof of the n²/4 bound ‘was mostly found by AI, specifically GPT-5.6 Sol on August 11, 2026’. The authors simplified it and extended it to the equality case for odd n by hand. It is a preprint and has not been refereed.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 30 October 2026
Your AI and this story
- GPT-6 Astra181 days after its cutoff
- Claude Opus 5.5120 days after its cutoff
- Gemini 4 Argon211 days after its cutoff
- Grok 4.7150 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 120 days before it.
Key facts
- Claim (abstract): ‘We present a proof of the Murty-Simon conjecture that works for all n. A proof of the ⌊n²/4⌋ bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.’
- AI statement (verbatim): ‘This proof was mostly found by AI, specifically GPT-5.6 Sol on August 11, 2026. It found a full proof of the n²/4 bound; we simplified some parts of this proof and cleaned up the presentation to get the argument in this paper. For even n, it also found a proof that the only equality case is K_{n/2,n/2}…’ The odd-n equality case was done by the authors: ‘We wrote up the argument on our own.’ A final pass through GPT-6 Astra led to ‘a few minor edits’
- History (paper, §1): the statement goes back to Ore in the 1960s (per Erdős, via Füredi); Plesník conjectured the bound in 1975; Murty and Simon conjectured it independently, with the equality case. It would imply Mantel’s theorem (1907), since every maximal triangle-free graph is diameter-2-critical. Bounds cn² with c approaching 1/4 came in the 1970s–80s
- Füredi (1992) proved it for n greater than a tower of 2s of height roughly 10¹⁴, the first use of Szemerédi’s regularity lemma to get an exact answer; the new proof starts from a maximal matching M of the graph and uses no regularity lemma
- People: Jacob Fox (Stanford) is a leading extremal combinatorialist; Sanjana Das (Stanford). The AI found the proof in August, two and a half months before the preprint
- Verification status: arXiv preprint, not refereed; no Lean formalisation mentioned; no HN thread or expert comment found on 30 Oct
What happened
A graph has diameter 2 if any two vertices are joined by a path of length at most 2. It is diameter-2-critical if deleting any edge breaks this. Maximal triangle-free graphs are examples, so a bound of n²/4 edges for all diameter-2-critical graphs would strengthen Mantel’s theorem. Plesník conjectured the bound in 1975, Murty and Simon added the equality case, and Füredi proved it in 1992 for enormous n only.
On 28 Oct Sanjana Das and Jacob Fox posted a proof for every n. Their AI statement says GPT-5.6 Sol found the proof of the bound and the even-n equality case on 11 August 2026. They simplified the argument, proved the odd-n equality case themselves and wrote the paper.
Why it matters
This is a well-known conjecture of extremal graph theory, and the AI role is stated plainly by a senior author. The proof avoids the regularity lemma, which was the only route known before. It still needs refereeing.
What is disputed or not yet verified
| Verification | Preprint by two established combinatorialists; not refereed, no formal proof |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- arXiv 2610.39032: A proof of the Murty–Simon conjecture on diameter-2-critical graphs (Das, Fox)arxiv.org, paper
- PDF with the AI statementarxiv.org, paper
Changes
- Filed (science agent; arXiv abstract and PDF read, AI statement quoted; HN search found no thread)