Skip to content

Erdős Problem #815

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

Fix k>=3. For sufficiently large n, does every n-vertex graph with 2n-2 edges and with every proper INDUCED subgraph having minimum degree <=2 necessarily contain a cycle of length exactly k? These are degree-3-critical graphs. The universal all-k claim is DISPROVED, but the restriction to even k remains OPEN.

A small example

For K4, every proper induced subgraph is K3 or smaller and therefore has minimum degree <=2, but K4 has 6 edges while 2n-2=6 and cycles of length 3 and 4, not 23. Small K4 does NOT test the 'sufficiently large n' counterexample; use only as exact structural fixture.

What is known

Maintained https://www.erdosproblems.com/latex/815, read 2026-10-14: Erdős–Faudree–Gyárfás–Schelp [EFGS88] prove C3,C4,C5 present for all such n>=5, plus cycle of length at least floor(log_2 n); Erdős 1991 attributes cycles 3..6 to himself and Hajnal. Narins–Pokrovskiy–Szabó [NPS17], Graphs without proper subgraphs of minimum degree 3 and short cycles, Combinatorica 2017, 495–519, construct arbitrarily large examples with no C23. The all-even-k strengthening remains an open separate question. The authors' open version and journal record independently confirm a general disproof, but the exact special C23 construction and all-even scope still require a targeted primary section replay.

The counterexample excludes the specific odd cycle \(C_{23}\) for arbitrarily large admissible orders. This is consistent with the historical guarantee of some cycle of length at least \(\lfloor\log_2 n\rfloor\): a long cycle need not have length 23. The restriction to every fixed EVEN \(k\) is a distinct open claim, not an automatic consequence of the published negative theorem.

The extremal hypotheses require exactly \(2n-2\) edges, and the induced subgraph condition concerns every proper vertex subset. A statement that some cycle has length at least \(\lfloor\log_2n\rfloor\) does not imply existence of a cycle of any prescribed length. The known forbidden \(C_{23}\) examples are consistent with that logarithmic-long-cycle theorem; the even-length restriction remains open.

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: Long odd-cycle prohibition (such as C23) disproves the broad conjecture, while the all-even-length refinement remains open.

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

Implement degree-3-critical predicate (for every proper nonempty induced subset, min degree <=2), verify K4, and inspect NPS17 construction with odd-cycle length 23 and its order quantifier. Do not state every even k solved or confuse 'some long cycle' with prescribed Ck.

The publisher abstract verifies the general negative result, but editorial admission still requires checking the specific C23 and even-length claims against the complete original proof.

Sources and claim boundaries

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: #2086 — 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.

Back to catalogue · Compendium introduction