Skip to content
DraconiticResearch
Search Sources API
206,690 studies31 sourcesUpdated 18 min ago
PreprintCC BY 4.0arXiv

A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs

  • Sanjana Das
  • Jacob Fox
Open at sourcePDFDOICite

Abstract

The Murty-Simon conjecture states that every n-vertex diameter-$2$-critical graph has at most ⌊ n2/4 ⌋ 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 1014). We present a proof of the Murty-Simon conjecture that works for all n. A proof of the ⌊ n2/4 ⌋ bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.

Related

  1. A proof of the resistance diameter conjecture for line graphs
    Xiang-Feng Pan, Xiang-Yang Liu, Zhen-Mu Hong
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On Diameter Graphs Problems: A proof of Brass's Conjecture
    Gyivan Lopez-Campos
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  3. Proof of the Göbel-Veldman conjecture on diametrical graphs
    Xingzhi Zhan
    HALPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL
  4. A Proof of the Tratnik-Ye Medianity Conjecture of Resonance Graphs on Surfaces
    Guangfu Wang, Ke Kang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A Complete Proof of the Strong Conjecture about F-Irregular Graphs
    Tatiana Dovzhenok, Artem Filuta
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{das2026proof,
  title = {{A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs}},
  author = {Sanjana Das and Jacob Fox},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.39032},
  eprint = {2610.39032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39032},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
AU  - Sanjana Das
AU  - Jacob Fox
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.39032
UR  - https://arxiv.org/abs/2610.39032
AB  - The Murty-Simon conjecture states that every n-vertex diameter-$2$-critical graph has at most ⌊ n^2/4 ⌋ 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 ⌊ n^2/4 ⌋ bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.
ER  -