Erdős Problem #742
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: decidable (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A finite graph G on n vertices is diameter-two EDGE-CRITICAL if diam(G)=2 and deleting ANY one edge increases its diameter (possibly to infinity). Murty–Simon ask whether |E(G)|≤floor(n²/4) for every such graph. The maintained catalogue says DECIDABLE rather than PROVED: Füredi establishes the inequality for all sufficiently large n, leaving finitely many n to check. The full all-n statement must NOT be promoted to a theorem merely from the sufficiently-large result.
A small example
For n=5, K_{2,3} has 6 edges, diameter 2, and deleting any cross-edge makes its endpoints distance 3. Thus it is diameter-two edge-critical and has 6=floor(25/4) edges. In general K_{a,b} with a+b=n, a,b≥2, gives ab≤floor(n²/4), with equality for balanced parts.
What is known
Füredi [Fu92] proves the Murty–Simon inequality for n≥n0. The pinned FormalConjectures/ErdosProblems/742.lean distinguishes an all-n main theorem using answer(sorry), a Füredi sufficiently-large theorem with sorry, and partial finite n≤24 and n=26 theorem statements also with sorry. The main universal status is DECIDABLE in the catalogue, meaning reduced to finitely many cases, NOT necessarily that those cases have been exhausted. A 2025 forum note from Terence Tao explicitly emphasizes that the finite residual verification remains open. All GCL-pinned theorem bodies do not constitute kernel certificates.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Furedi proves all sufficiently large n; catalogue DECIDABLE is reduction to finite checking, not proof of all finite exceptions.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
ERDOS-742-MURTY_SIMON-FINITE_GAP. Reproduce exact K_{2,3} edge-critical fixture, audit Füredi's n0 and exceptional finite cases, and enumerate graph isomorphism classes only within a proven manageable bound. Acceptance is a finite exhaustive certificate or a source-locked statement of the remaining check; no complete universal proof without it.
Sources and claim boundaries
Maintained Erdős #742; original issue-bound GCL audit. Primary full proof pages not all inspected; no newly certified theorem proof, real browser mathematics validation or V2 admission.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2013 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.