Erdős Problem #57
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, chromatic number, 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
Erdős Problem 57 concerns the distribution of odd cycle lengths in a graph whose chromatic number is infinite. If \(A_{\mathrm{odd}}(G)\) denotes the set of distinct odd integers occurring as cycle lengths, the question is whether
must diverge.
This is stronger than merely asking for infinitely many odd cycle lengths. A very sparse infinite set can have a convergent reciprocal sum, so the problem asks for quantitative richness in the cycle spectrum.
The problem does not count cycles with multiplicity. For example, if a graph contains many triangles, the length \(3\) contributes only once.
A small example
Erdős and Hajnal’s 1966 Theorem 7.7 says, in modern notation, that if a finite-chromatic graph has no odd cycle of length \(2i+1\) for any \(i\ge j\), then its chromatic number is at most \(2j\). The bound is sharp: \(K_{2j}\) has chromatic number \(2j\) and contains no odd cycle longer than \(2j-1\).
This verifies the intended quantifier pattern and shows why “infinitely many odd lengths” is substantially weaker than reciprocal-sum divergence.
A second elementary check uses complete graphs. Since \(K_n\) contains a cycle on every selected set of at least three vertices, its odd cycle lengths are precisely the odd integers from \(3\) through \(n\). Hence
Thus the coefficient \(1/2\) in the Liu–Montgomery lower bound is asymptotically natural.
What is known
The exact reciprocal-sum formulation is visible in Erdős’s 1981 paper Problems and Results in Graph Theory. In its miscellaneous problems section, Erdős writes that Hajnal and he conjectured divergence of the reciprocal sum over the odd circuit lengths of an infinite-chromatic graph. He immediately adds the stronger speculation that these lengths might have positive upper density. Erdős 1981, p. 339
The frequently attached 1966 citation is historically relevant but not textually identical. Erdős and Hajnal’s 1966 paper proves that infinite chromatic number forces infinitely many odd cycle lengths and asks whether all sufficiently large odd lengths must occur. That is a predecessor problem, not the registered reciprocal-sum statement. Erdős–Hajnal 1966, §7
This distinction matters for provenance auditing: the mathematical status is settled, but the catalogue’s short citation should not be treated as proof that the exact displayed statement first appeared in 1966.
Liu and Montgomery prove a considerably stronger finite statement. For every fixed \(\varepsilon>0\) and all sufficiently large chromatic numbers \(k\), a graph of chromatic number \(k\) contains every odd cycle length in an interval
for some \(\ell\) depending on the graph.
The reciprocal sum over odd integers in such an interval is approximately
Letting \(\varepsilon\) tend to zero gives their quantitative conclusion
The theorem is stated and proved in Liu–Montgomery, and the published version is JAMS 36 (2023), DOI 10.1090/jams/1018.
The original problem allows \(G\) itself to be infinite. The relevant compactness principle is the de Bruijn–Erdős theorem: if an infinite graph has no finite subgraph of chromatic number exceeding \(k\), then the whole graph is \(k\)‑colorable.
Therefore, if \(\chi(G)\) is infinite, then for every finite \(k\) there is a finite subgraph \(H\subseteq G\) with chromatic number at least \(k\). Applying the Liu–Montgomery estimate to \(H\) gives
Since the right-hand side is unbounded as \(k\to\infty\), the sum for \(G\) diverges.
This also explains why the finite theorem is the correct interface for the infinite statement: no separate infinite-graph construction is needed once compactness is available.
GCL's current state
As of 2026-10-12, the maintained catalogue status is PROVED. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.
Prerequisite: retain the 1981 primary statement as the exact-source lock and mark [ErHa66] as a related-source attribution requiring catalogue review.
No mathematical blocker remains: the published Liu–Montgomery theorem resolves the registered statement. Formal-proof status remains unverified; the current formal file is statement-level evidence only. Existing OUTSIDE_STRICT_OPEN_TRIAGE and campaign restrictions are preserved.
The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.
What remains
Input: the formal statement in FormalConjectures/ErdosProblems/57.lean, together with the definitions of SimpleGraph.oddCycleLengths and chromatic number.
Target: formalize the finite sanity lemma
for \(n\ge3\), followed by the elementary lower bound
for an explicit absolute constant \(C\).
Method: first prove the exact cycle-length set equality; then derive the harmonic estimate from integral comparison. Acceptance requires a compiling Lean proof with no sorry in this bounded target and an explicit check that lengths are deduplicated. Falsification is triggered if the formal object counts individual cycles rather than lengths or uses a different odd-cycle convention. Stop after this semantic adapter and numerical bound; do not attempt to formalize the full Liu–Montgomery proof in this work package.
Sources and claim boundaries
Maintained problem #57; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
The exact reciprocal-sum problem appears in P. Erdős, Problems and Results in Graph Theory, printed p. 339, 1981, where Erdős and Hajnal ask whether the reciprocal sum over odd circuit lengths diverges and additionally speculate about positive upper density. Primary scan
The cited 1966 Erdős–Hajnal paper is a related antecedent, but its exact §7 problem is different: Problem 7.6 asks whether all sufficiently large odd lengths must occur; Theorem 7.5 proves only infinitely many odd lengths, and Theorem 7.7 gives a sharp bounded-odd-cycle chromatic estimate. Primary scan Thus the catalogue/formal-file attribution [ErHa66] should be retained as catalogue metadata but flagged as provenance drift for the exact wording.
Hong Liu and Richard Montgomery resolve the registered statement. Their accepted manuscript, v2 dated 19 September 2022, states Theorem 1.4 on manuscript p. 3 and proves it on pp. 39–40; the result was published in JAMS 36 (2023), 1191–1234, DOI 10.1090/jams/1018. Primary manuscript
The provided issue.json records catalogue status proved, last update 2025-08-31, and reported Lean availability. The provided live.html is a 23 January 2026 snapshot and says the statement is formalized. The current public formal file contains the solved-category annotation but its theorem body still contains sorry; no formal proof was independently compiled. Formal statement file
Reused evidence: the provided issue.json, the provided live.html, the Erdős–Hajnal 1966 scan, the Erdős 1981 scan, and the Liu–Montgomery primary manuscript. No sibling returns were inspected. I did not post, commit, certify, or independently reprove the Liu–Montgomery theorem.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1326 — 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.