Erdős Problem #63
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
A graph needs many colors if adjacent vertices must always have different colors. Erdős and Mihók asked whether a graph needing infinitely many colors must contain cycles whose lengths are powers of two, not merely once, but for infinitely many different powers.
For example, an eight-edge cycle has length \(2^3\), and a sixteen-edge cycle has length \(2^4\). The question is whether infinitely many such lengths must occur in every graph of infinite chromatic number.
A small example
A finite graph with chromatic number \(r\) has a subgraph of minimum degree at least \(r-1\). To see this, repeatedly delete vertices having at most \(r-2\) neighbors. If the entire graph disappears, color the deleted vertices in reverse order with \(r-1\) colors. Each vertex sees at most \(r-2\) previously colored neighbors, so this would color the original graph with \(r-1\) colors, a contradiction.
For instance, the complete graph \(K_5\) has chromatic number five and minimum degree four. The lemma turns a demand for many colors into a dense finite subgraph. It does not, by itself, produce a cycle of any specified length.
What is known
The answer is yes. Liu and Montgomery proved a much stronger result about even cycle lengths. Their Theorem 1.1 says that a graph of sufficiently large average degree \(d\) has every even cycle length in an interval from \((\log\ell)^8\) to \(\ell\), for some \(\ell\ge d/(10\log^{12}d)\). Their Corollary 1.3 directly treats sequences of even integers growing at most exponentially, including powers of two. See Liu–Montgomery, arXiv:2010.15802v2.
Why does this solve the infinite-chromatic problem? By the de Bruijn–Erdős compactness theorem, an infinitely chromatic graph contains finite subgraphs of arbitrarily large chromatic number. The deletion lemma above extracts finite subgraphs with arbitrarily large average degree. Liu–Montgomery then supplies long intervals of even cycle lengths. For large enough \(\ell\), such an interval contains a power of two beyond any chosen bound. Repeating with larger bounds yields infinitely many distinct powers.
GCL's current state
The pinned catalogue and maintained Erdős Problems page classify #63 as PROVED. The local editorial work identifies the exact Liu–Montgomery theorem and an elementary core lemma connecting chromatic number to average degree. The original assignment is ERDOS-CATALOGUE-0063-S01.
The catalogue reports a Lean formalization, but no kernel replay or equivalence audit is claimed here. This article is an unaccepted local draft pending an authenticated source return.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded formalization task is to prove the finite core lemma and the elementary statement that the interval \([(\log\ell)^8,\ell]\) contains arbitrarily large powers of two as \(\ell\) grows. The deep cycle-length theorem should be imported with its precise hypotheses; replacing it by an unproved intuition about dense graphs would be invalid.
Sources and claim boundaries
- Liu and Montgomery, A solution to Erdős and Hajnal's odd cycle problem, Theorem 1.1 and Corollary 1.3, revision 19 September 2022.
- Maintained Erdős problem #63, captured 2026-10-12; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
- GCL original source issue #1332.
No new theorem, Lean certification or editorial acceptance is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1332 — 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.