A proof of the Murty--Simon conjecture on diameter--critical graphs
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 13 pages