A proof of the Murty--Simon conjecture on diameter--critical graphs
In the authors' words
The Murty-Simon conjecture states that every -vertex diameter--critical graph has at most edges, with equality only for the balanced complete bipartite graph. Using regularity methods, F\"uredi proved this for all sufficiently large (specifically, greater than a tower of 's of height roughly ). We present a proof of the Murty-Simon conjecture that works for all . A proof of the bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.
Main resultThe abstract does not state a limitation.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 13 pages