{"id":"arxiv/2610.39032","url":"https://arxiv.org/abs/2610.39032","tags":["math.CO"],"score":0,"title":"A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs","domain":"math.CO","source":"arxiv","authors":["Sanjana Das","Jacob Fox"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-28","reactions":{}}