Skip to content

Erdős Problem #71

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

Pick an infinite arithmetic progression of positive integers \(P=\{a+jd:j\ge0\}\) that includes some even integer. Erdős #71 asks whether there is a constant \(c(P)\) such that every graph with average degree at least \(c(P)\) contains a cycle whose length lies in \(P\).

Average degree is \(2e(G)/|V(G)|\). The cycle is required to have one of the specified lengths, not merely a length with the correct parity.

A small example

The complete graph \(K_4\) has four vertices and six edges, so its average degree is three. It has a cycle of length four, belonging to the progression \(4,6,8,\ldots\). This is a finite illustration, not a universal density theorem.

The hypothesis that \(P\) contains an even term is necessary. The complete bipartite graph \(K_{m,m}\) has average degree \(m\) and no odd cycle, even when \(m\) is arbitrarily large. A progression consisting exclusively of odd numbers can therefore never be forced by any fixed average-degree threshold.

What is known

The answer is YES. Béla Bollobás proved the conjecture in Cycles Modulo k (1977). The original publisher record identifies the two-page note in Bulletin of the London Mathematical Society 9, 97–98. Liu and Montgomery's modern primary introduction independently attributes the arithmetic-progression theorem to Bollobás. The maintained problem page confirms the exact registered application and observes that the best quantitative dependence of \(c(P)\) on \(P\) is still unknown.

There is a subtle parity distinction: when \(d\) is odd, a progression beginning with an odd term also includes even terms. Replacing “contains an even integer” with “every term even” would incorrectly weaken the historical theorem.

GCL's current state

The original assignment is ERDOS-CATALOGUE-0071-S01. The 1977 primary bibliographic record and the 2022 Liu–Montgomery historical attribution have been checked. The actual two-page argument is behind a publisher access boundary in this pass, so no claim of a complete primary-proof audit or explicit threshold \(c(P)\) is made. This is a pending editorial draft.

The original GitHub issue now contains the authenticated RESULT/1 source report. This does not imply independent mathematical review or editorial admission.

What remains

Obtain the 1977 note and extract its precise modulus and residue theorem, including restrictions on finite graphs, cycle lengths and average degree. Then prove that any progression with an even term fits the exact theorem, without changing initial indices. A bounded test case uses an odd starting value and odd difference, and a negative control uses an all-odd progression and \(K_{m,m}\). Proof access is a source-fidelity exception, not evidence that the mathematical result is open.

Sources and claim boundaries

No independent certification of Bollobás's proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1340 — 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.

Back to catalogue · Compendium introduction