Erdős Problem #751
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, chromatic number.
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
In a graph with chromatic number four, list distinct lengths of all cycles in increasing order. Erdős asked if their successive gaps can all be made arbitrarily large, perhaps even when the girth grows. Bondy–Vince 1998 DISPROVED the possibility: every graph with minimum degree≥3 has two cycles with distinct lengths differing by at most two; every 4-chromatic graph contains a 4-critical subgraph of minimum degree≥3, so its cycle-length set contains two lengths with gap at most two. This works independently of girth.
A small example
The graph K4 is 4-chromatic and has cycles of lengths 3 and 4, so its minimum gap between distinct cycle lengths is one. This is a finite witness, not the Bondy–Vince universal theorem. For every 4-critical graph H, each vertex must have degree≥3: a vertex of degree≤2 could be removed, the rest 3-coloured, and the colouring extended, contradicting χ(H)=4.
What is known
Primary research due to Bondy and Vince [BoVi98], 'Cycles in a graph whose lengths differ by one or two' (source title/venue need complete primary-page confirmation). The maintained page says DISPROVED (LEAN), linking a reported external formalization in a separate university/independent repository; no #751.lean is in the GCL-protected pinned FC snapshot and no Lean proof/axiom closure was internally replayed. The reduction through 4-critical subgraphs is an elementary standard lemma, but source attribution of the universal cycle theorem remains Bondy–Vince.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: bondy vince cycle gaps disproves; external lean not gcl verified. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
ERDOS-751-BONDY_VINCE_CYCLE_GAPS. Verify primary 1998 theorem's exact minimum-degree assumptions and whether it ensures lengths differ by ONE OR TWO. Independently formalize the 4-critical min-degree≥3 reduction, enumerate K4 3/4 cycles, and audit external Lean dependency hashes before certification.
Sources and claim boundaries
Maintained Problem #751; original GCL issue return. Full historical proof papers and external Lean kernels unreviewed. no new independent primary theorem certification or editorial admission.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2022 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.