Skip to content

Erdős Problem #74

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

Could a graph require infinitely many vertex colors while every finite part becomes bipartite after deleting only a few edges? Erdős #74 asked whether this is possible for every prescribed function \(f(n)\to\infty\), however slowly it grows. The graph may depend on \(f\); each finite \(n\)‑vertex subgraph must need at most \(f(n)\) edge deletions.

A small example

A triangle becomes bipartite after deleting one edge, but the disjoint union of arbitrarily many triangles is only three-colorable. Few edge deletions in each small subgraph do not automatically produce high chromatic number. Quantifiers over all finite subgraphs matter.

For a graph \(G\) write \(b_G(n)\) for the maximum, over finite \(n\)‑vertex subgraphs \(H\), of the minimum number of edges whose removal makes \(H\) bipartite. The conjecture asserts the existence of infinite-chromatic \(G\) with \(b_G(n)\le f(n)\) for every divergent \(f\).

What is known

The universal assertion is classified DISPROVED. A 2026 Lean proof package associated with Tom Adamczewski's FrontierMath Erdős benchmark has a compared statement showing

\[ \neg\bigl[\forall f\to\infty,\;\exists G:\chi(G)=\infty \text{ and }\forall n,\;b_G(n)\le f(n)\bigr]. \]

Equivalently, there is at least one divergent rate \(f\) for which all qualifying graphs have finite chromatic number. The source package describes proofs of a stronger three-colorability result, but the theorem compared in Challenge.lean asserts only finite chromatic number, and the proposed explicit asymptotic rate is not part of its formal target.

GCL's current state

GCL read the primary Lean statement and edge-distance definitions from the immutable source commit a626ecc. Neither Lean execution nor comparator/axiom checks have been independently reproduced by GCL. The original task is ERDOS-CATALOGUE-0074-S01. The pinned catalogue's negative status is source metadata, not independent GCL certification.

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

What remains

The bounded verification target is to run the pinned Lean build and statement comparator, inspect axiom dependencies, and check semantics against the original graph-theoretic formulation. In particular, the helper definitions take minima over edge deletions and maxima over all finite subgraph candidates (not only induced ones); finite/infinite vertex types and the quantifier order must match precisely.

Sources and claim boundaries

No independent proof certification or editorial acceptance is claimed.

Catalogue and evidence provenance

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