Skip to content

Erdős Problem #55

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

A graph needs infinitely many colours if no finite collection of colours can assign different colours to adjacent vertices. Such a graph must contain odd cycles, since a graph without any odd cycle is bipartite and two-colourable. But how many different odd lengths must occur?

Erdős Problem #55, attributed to Erdős and Hajnal, asks whether the reciprocal sum of the distinct odd cycle lengths in every graph with infinite chromatic number must diverge:

\[ \sum_{\ell\in C_{\mathrm{odd}}(G)}\frac1\ell=\infty. \]

The answer is yes, proved by Hong Liu and Richard Montgomery.

A small example

In the complete graph on seven vertices, cycles occur at odd lengths 3, 5 and 7. The sum of the reciprocals of those distinct lengths is

\[ \frac13+\frac15+\frac17=\frac{71}{105}. \]

If a graph contains 500 triangles, the contribution from length three is still only \(1/3\): the theorem counts lengths, not individual cycles.

What is known

Liu and Montgomery, A solution to Erdős and Hajnal's odd cycle problem, Journal of the American Mathematical Society 36 (2023), 1191–1234, prove the stronger quantitative estimate

\[ \sum_{\ell\in C_{\mathrm{odd}}(G)}\frac1\ell \ge\left(\frac12-o_k(1)\right)\log k \]

for graphs of chromatic number \(k\) as \(k\) increases. One ingredient is their Theorem 1.4, which ensures that every odd integer in a long multiplicative interval occurs as a cycle length. Since about half the integers in a long interval are odd, its reciprocal sum grows with leading coefficient one-half, not one.

An infinite-chromatic graph contains finite subgraphs with arbitrarily large chromatic number, by the compactness theorem for finite graph colouring. Those finite subgraphs inherit their cycle lengths from the original graph, so the quantitative bound forces an unbounded reciprocal sum.

GCL's current state

Authenticated source audit #1324 pins the Liu–Montgomery source theorem, its finite-versus-infinite reduction and the exact complete-graph calculation. The mathematical problem is settled in the published literature; the proof has not been independently re-created or kernel-certified by GCL.

What remains

The original divergence problem is resolved. Further work can formalize the compactness and reciprocal-sum deductions from a precisely source-pinned finite-chromatic theorem. That is a limited formalization target, not a new answer to Erdős and Hajnal.

Sources and claim boundaries

Catalogue and evidence provenance

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