Skip to content

Erdős Problem #58

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

Let \(L_o(G)\) be the set of lengths of odd cycles in a finite simple graph \(G\). Erdős Problem 58 asks whether

\[ |L_o(G)|\le k \quad\Longrightarrow\quad \chi(G)\le2k+2, \]

with equality only when \(G\) contains \(K_{2k+2}\).

The problem is sourced to Erdős’s 1990 chapter “Some of my favourite unsolved problems.” The exact chapter is bibliographically accessible, but its full text was unavailable here. Gyárfás’s primary 1992 paper explicitly records the attribution to Bollobás and Erdős and gives the relevant definition of \(L_o(G)\).

Gyárfás proved a stronger structural theorem: if a 2-connected graph has minimum degree at least \(2k+1\) and exactly \(k\) odd cycle lengths, then it is \(K_{2k+2}\). Applying this to the blocks of a graph gives

\[ \chi(G)\le2k+2, \]

and shows that equality forces a complete block \(K_{2k+2}\). The converse is immediate because \(K_{2k+2}\) has chromatic number \(2k+2\).

The numerical bound is sharp. In \(K_{2k+2}\), every cycle length from \(3\) through \(2k+2\) occurs, so the odd lengths are exactly

\[ 3,5,\ldots,2k+1, \]

which are \(k\) lengths. Thus \(\chi(K_{2k+2})=2k+2\) realizes equality.

Gao, Huo, and Ma later strengthened the result: chromatic number at least \(2k+3\) forces \(k+1\) consecutive odd cycle lengths. This confirms that the original theorem is part of a stronger relation between chromatic number and the distribution of cycle lengths.

The catalogue’s current Lean file formalizes the statement but contains sorry; it should therefore be described as statement-formalized, not proof-verified.

Sources: Erdős 1990, Gyárfás 1992, Gao–Huo–Ma 2021, and the current formal statement.

Normalization and edge case

The phrase “at most \(k\) different odd cycle lengths” means cardinality:

\[ |L_o(G)|\le k, \]

not that every odd cycle has length at most \(k\). The parameter \(k\) is an integer, and \(G\) is a simple graph. The source theorem is stated for \(k\ge1\); the case \(k=0\) is elementary.

For \(k=0\), \(G\) has no odd cycle. In each connected component, choose a root and color each vertex by the parity of its distance from the root. An edge joining equal parities would create an odd closed walk and hence an odd cycle. Therefore \(G\) is bipartite and \(\chi(G)\le2\).

A small example

For \(G=K_{2k+2}\), every integer cycle length \(r\) with \(3\le r\le2k+2\) occurs. The odd ones are

\[ 3,5,\ldots,2k+1. \]

Their number is

\[ \frac{(2k+1)-3}{2}+1=k. \]

Also,

\[ \chi(K_{2k+2})=2k+2. \]

Thus the upper bound cannot be improved.

Concrete check: for \(k=2\), \(K_6\) has odd cycle lengths \(\{3,5\}\), exactly two lengths, and chromatic number \(6=2\cdot2+2\).

For \(k=1\), \(K_4\) has exactly one odd cycle length, \(3\), and chromatic number \(4=2k+2\). For \(k=0\), \(K_2\) has no odd cycle and chromatic number \(2\).

What is known

Gyárfás’s Theorem 1 states that a 2-connected graph \(G\) with

\[ \delta(G)\ge2k+1 \quad\text{and}\quad |L_o(G)|=k\ge1 \]

must satisfy

\[ G=K_{2k+2}. \]

The proof uses a longest odd cycle and analyzes how vertices outside it attach. If the graph were not complete, the attachment patterns generate more than \(k\) distinct odd cycle lengths, contradicting the hypothesis.

This is the main reusable interface: a high minimum degree inside a 2-connected block forces the extremal complete graph.

Every graph decomposes into blocks. Gyárfás’s corollary says that if \(|L_o(G)|=k\), then every relevant block is colorable with at most \(2k+1\) colors unless it is \(K_{2k+2}\). A complete block has chromatic number \(2k+2\).

Hence

\[ \chi(G)\le2k+2. \]

If equality holds, some block must be \(K_{2k+2}\), so \(G\) contains that clique. Conversely, containing \(K_{2k+2}\) forces chromatic number at least \(2k+2\), and the upper bound forces equality.

For “at most \(k\)” lengths, apply the result to the actual number \(j=|L_o(G)|\le k\).

Gao, Huo, and Ma prove that if

\[ \chi(G)\ge2k+3, \]

then \(G\) contains \(k+1\) consecutive odd cycle lengths. In particular, a graph avoiding all but \(k\) odd lengths cannot have chromatic number \(2k+3\) or larger.

This is stronger than merely counting odd lengths: it forces a consecutive interval in the odd-length spectrum.

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.

Source lock is sufficient for the mathematical result through Gyárfás’s accessible primary paper. The exact internal page of the original Erdős chapter is unavailable, and the current formal proof is unavailable (sorry).

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 current 58.lean statement and the finite simple graph definitions.

Target: formally verify the sharpness witness

\[ L_o(K_{2k+2})=\{3,5,\ldots,2k+1\}, \qquad |L_o(K_{2k+2})|=k, \qquad \chi(K_{2k+2})=2k+2. \]

Method: prove the cycle-length enumeration by selecting \(r\) vertices for each \(3\le r\le2k+2\), then check \(k=0,1,2\) by explicit finite instances.

Acceptance: compilation with no sorry in the new lemma and successful checks for \(K_2\), \(K_4\), and \(K_6\).

Falsification hook: failure would indicate a mismatch in the Lean definition of odd-cycle length, complete-graph containment, or chromatic number.

Stopping rule: stop after the witness lemma and the three finite checks; do not attempt to formalize Gyárfás’s full proof in this bounded task.

Sources and claim boundaries

Maintained problem #58; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.

  • The supplied live.html, captured 2026-10-12, labels the problem PROVED.
  • The pinned catalogue revision in the issue packet, commit 536408716724a2402bdfa7c1d764bf83d64a8c89 dated 2025-08-31, also labels it proved, while reporting the formal solution as unavailable.
  • The original source is P. Erdős, “Some of my favourite unsolved problems,” in A Tribute to Paul Erdős, 1990, pp. 467–478. The Cambridge record confirms the chapter and DOI 10.1017/CBO9780511983917.039.
  • The full Erdős chapter was not accessible in this run, so its exact internal page containing Problem 58 is unavailable. I do not infer wording from it.
  • The accessible primary proof is A. Gyárfás, “Graphs with \(k\) odd cycle lengths,” Discrete Mathematics 103 (1992), 41–48. Its introduction explicitly attributes the question to Bollobás and Erdős, defines \(L_o(G)\), and states the conjectured bound. Theorem 1 and the corollary are on p. 42 of the author-hosted paper.
  • Gyárfás proves: if \(G\) is 2-connected, has minimum degree at least \(2k+1\), and \(|L_o(G)|=k\ge1\), then \(G=K_{2k+2}\). Consequently, if \(|L_o(G)|=k\), then \(\chi(G)\le2k+1\) unless a block is \(K_{2k+2}\); in that exceptional case \(\chi(G)=2k+2\).
  • Gao, Huo, and Ma strengthen the result: if \(\chi(G)\ge2k+3\), then \(G\) contains \(k+1\) consecutive odd cycle lengths. See arXiv:2012.10624, Theorem 1.1 and the SIAM record.

Current drift: the live page now links a formalized statement, but the current Lean theorem still ends in by sorry; therefore the statement is formalized, not proof-verified. The unavailable formal proof is PARTIAL.

Reused the issue’s pinned catalogue metadata and the supplied live snapshot for status comparison. Independently checked the clique sharpness calculation and the no-odd-cycle bipartition lemma below. No formal proof, publication claim, novelty claim, award claim, or independent verification of the Lean theorem is asserted.

Catalogue and evidence provenance

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