A finite check of the Murty-Simon lemmas of Das-Fox on all diameter-2-critical graphs with at most 11 vertices (a sanity check of claims by others)

Das and Fox (arXiv:2610.39032, 28 Oct 2026, unrefereed) claim a proof of the Murty-Simon conjecture: a diameter-2-critical (D2C) graph on n vertices has at most floor(n2/4) edges. Two of their lemmas are unconditional statements about all D2C graphs: Lemma 1.2 (for every maximal matching M, |E \ M| is at most the number of non-edges) and Lemma 1.3 (if equality holds for every maximal matching, the graph is triangle-free). The proof is theirs. This is a finite sanity check of claims by others; we claim nothing new and do not verify the proof. What was checked (Tier C: exact integer arithmetic, two independent implementations). All 4,419 D2C graphs with 3 ≤ n ≤ 11 (counts 1, 2, 3, 5, 10, 30, 103, 519, 3746) and all 776,217 of their maximal matchings: 0 violations of Lemma 1.2, Lemma 1.3 or Theorem 1.1. The maximum number of edges floor(n2/4) is attained uniquely by the balanced complete bipartite graph. Exactly one graph per n is an equality case for all maximal matchings (balanced Ka,b, triangle-free), so Lemma 1.3 is nearly vacuous in this range; D2C graphs with a triangle stay below the bound of Lemma 1.2 by at least 1 at n = 6 and at least 10 at n = 11. The counts equal OEIS A330333, so the census is a recomputation, and Theorem 1.1 was already reported proved for n ≤ 24 and n = 26 (Fan 1987, as reported by Dailly-Foucaud-Hansberg). Audit. A separate AI agent instance (not a human) reproduced the census with its own Rust code, including a fresh enumeration of all 1,006,700,565 connected graphs on 11 vertices (ACCEPT_WITH_CORRECTIONS; eight corrections applied). Limitations. The Das-Fox proof is not verified; the intermediate lemmas 2.4, 2.5, 2.13, 3.1, 3.2 were checked by the producer only; nothing is claimed for n ≥ 12; the preregistration was committed together with the results (self-attested); no Lean; no human audit. The paper's full text is third-party and is not redistributed.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-01
DOI
https://doi.org/10.5281/zenodo.23864743
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A finite check of the Murty-Simon lemmas of Das-Fox on all diameter-2-critical graphs with at most 11 vertices (a sanity check of claims by others)

Xavier Callens
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

A finite check of the Murty-Simon lemmas of Das-Fox on all diameter-2-critical graphs with at most 11 vertices (a sanity check of claims by others)

Xavier Callens
preprint en

Abstract

Das and Fox (arXiv:2610.39032, 28 Oct 2026, unrefereed) claim a proof of the Murty-Simon conjecture: a diameter-2-critical (D2C) graph on n vertices has at most floor(n2/4) edges. Two of their lemmas are unconditional statements about all D2C graphs: Lemma 1.2 (for every maximal matching M, |E \ M| is at most the number of non-edges) and Lemma 1.3 (if equality holds for every maximal matching, the graph is triangle-free). The proof is theirs. This is a finite sanity check of claims by others; we claim nothing new and do not verify the proof. What was checked (Tier C: exact integer arithmetic, two independent implementations). All 4,419 D2C graphs with 3 ≤ n ≤ 11 (counts 1, 2, 3, 5, 10, 30, 103, 519, 3746) and all 776,217 of their maximal matchings: 0 violations of Lemma 1.2, Lemma 1.3 or Theorem 1.1. The maximum number of edges floor(n2/4) is attained uniquely by the balanced complete bipartite graph. Exactly one graph per n is an equality case for all maximal matchings (balanced Ka,b, triangle-free), so Lemma 1.3 is nearly vacuous in this range; D2C graphs with a triangle stay below the bound of Lemma 1.2 by at least 1 at n = 6 and at least 10 at n = 11. The counts equal OEIS A330333, so the census is a recomputation, and Theorem 1.1 was already reported proved for n ≤ 24 and n = 26 (Fan 1987, as reported by Dailly-Foucaud-Hansberg). Audit. A separate AI agent instance (not a human) reproduced the census with its own Rust code, including a fresh enumeration of all 1,006,700,565 connected graphs on 11 vertices (ACCEPT_WITH_CORRECTIONS; eight corrections applied). Limitations. The Das-Fox proof is not verified; the intermediate lemmas 2.4, 2.5, 2.13, 3.1, 3.2 were checked by the producer only; nothing is claimed for n ≥ 12; the preregistration was committed together with the results (self-attested); no Lean; no human audit. The paper's full text is third-party and is not redistributed.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
A finite check of the Murty-Simon lemmas of Das-Fox on all diameter-2-critical graphs with at most 11 vertices (a sanity check of claims by others) — Xavier Callens · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS