Skip to content

Erdős Problem #767

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, turan 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

Fix k≥1 and let g_k(n) be the largest number of edges of an n-vertex graph containing no cycle with k DISTINCT chords sharing one vertex on that cycle. Erdős conjectured that g_k(n)=(k+1)n−(k+1)² for sufficiently large n. Jiang [Ji04] proved the formula for n≥3k+3. The important threshold is n≥3k+3, not every n.

A small example

For k=1, a 4-cycle WITH a diagonal has one chord incident to each of its diagonal endpoints, and so is forbidden. The complete bipartite graph K_{2,n−2} has 2(n−2)=2n−4 edges and all cycles alternate between the two sides; each such cycle is a 4-cycle without chords (the bipartite graph has no within-side edges). Thus K_{2,n−2} realizes the exact lower 2n−4 for k=1. More generally K_{k+1,n−k−1} has (k+1)(n−k−1) edges and is a source-proposed extremal family; its full forbidden-configuration check needs clear cycle/chord convention.

What is known

Pósa proved g₁(n)=2n−4 for n≥4, Erdős established k=2,3 for n≥2k+2, and Jiang [Ji04] proved the general n≥3k+3 formula. Historic Erdős [Er69b] mentions a communicated Lewin counterexample 'for general k', apparently conflicting with the later theorem; possible small-n or statement-difference explanations require primary source inspection, not silent deletion of the historical note. The maintained 2025 #767 marks PROVED and recounts this conflict.

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: jiang 2004 n ge 3k plus3 proved; historic lewin disproof scope unresolved. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Check exact forbidden cycle with k chords sharing a cycle vertex, prove the K_{k+1,n−k−1} construction avoids it and yields the lower formula, and source-lock Jiang 2004 theorem's n≥3k+3 threshold plus the historical Lewin note. Distinguish induced versus ordinary chords.

Sources and claim boundaries

Maintained #767, authenticated original issue return. Complete original proof pages pending; no new independent primary theorem certification production merge, deployed browser mathematics QA 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: #2038 — 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