Erdős Problem #752
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, cycles.
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
For a graph G with minimum degree k and girth greater than 2s, Erdős, Faudree and Schelp asked if the graph must have at least c_s k^s distinct cycle lengths. This is PROVED by Sudakov and Verstraëte (2008). A stronger theorem assumes only average degree k and produces c_s k^s CONSECUTIVE EVEN cycle lengths; the hidden constant depends on fixed s.
A small example
The six-cycle C6 has minimum and average degree 2 and girth 6. For s=2, the hypothesis girth>4 holds, and C6 has exactly one cycle length, 6. This finite example cannot contradict an asymptotic lower bound with a small unspecified constant c_s and k fixed at 2. K_{k,k} has girth 4, so it does not satisfy s=2's strict girth>4 hypothesis.
What is known
Erdős–Faudree–Schelp proved s=2; Sudakov and Verstraëte [SuVe08] proved the general result. The maintained 2026 page says at least a constant times k^s consecutive even integers realized as lengths when minimum degree is weakened to average degree. 'Consecutive even integers' means ℓ,ℓ+2,…, not consecutive integers of both parities. Neither the original Sudakov–Verstraëte full proof nor its threshold on k,s was independently rederived in this GCL audit.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: Sudakov–Verstraëte consecutive EVEN cycle lengths under average degree, not every integer parity.
What remains
Read SuVe08 primary theorem, fix the dependence of constants and parity interpretation, and derive one exact small-girth lemma (e.g. in C6). Check the transition minimum→average degree. Report the full theorem's quantitative uniformity, without calling this a new GCL proof.
Sources and claim boundaries
Maintained Erdős #752, authenticated original issue return. Original source papers and any external Lean certificate not fully replayed; Primary mathematical proofs and any external Lean claims are not certified.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2023 — 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.