A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
The Murty-Simon conjecture states that every $n$-vertex diameter-$2$-critical graph has at most $\lfloor n^2/4 \rfloor$ edges, with equality only for the balanced complete bipartite graph. Using regularity methods, Füredi proved this for all sufficiently large $n$ (specifically, $n$ greater than a tower of $2$'s of height roughly $10^{14}$). We present a proof of the Murty-Simon conjecture that works for all $n$. A proof of the $\lfloor n^2/4 \rfloor$ bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.39032
curl -X POST /api/v1/records/arxiv/2610.39032/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.39032/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'