Skip to content

Erdős Problem #705

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, chromatic number.

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

For finite planar unit-distance graphs, does there exist a fixed girth threshold k such that every graph of girth at least k has chromatic number ≤3? The maintained catalogue says DISPROVED: O'Donnell in 1999 constructs 4-chromatic finite planar unit-distance graphs of arbitrarily large girth. Girth refers to shortest cycle length, not vertex count; the graph uses edges for EXACT distance one.

A small example

A regular unit equilateral triangle has girth 3 and chromatic number 3. This is not a counterexample to a high-girth 3-colourability claim. The Moser spindle has chromatic number 4 and short cycles, also insufficient. The required counterexamples must maintain χ≥4 while forcing the girth above ANY requested bound.

What is known

The maintained source credits Wormald 1979 with a 6448-vertex example of girth 5 and χ4, O'Donnell 1994 with a 56-vertex example of girth 4, and his 1999 Rutgers thesis 'High girth unit-distance graphs' with arbitrarily large girth and chromatic number four. The GCL-pinned FormalConjectures/ErdosProblems/705.lean directly inspected: theorem erdos_705 uses answer(False) ↔ the existence of such a universal k, but the proof body is 'by sorry'. Thus the FALSE status is recorded from O'Donnell's external mathematics, not pinned Lean certification. Full thesis proof not independently reconstructed.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: odonnell large girth disproof external; pinned fc by sorry. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Locate the O'Donnell 1999 main theorem and construction, verify graphs are unit-distance graphs in R² rather than arbitrary distance graphs, and test one small generated finite graph's girth/chromatic number. An externally reported theorem without an actual graph/embedding source lock remains bounded, not a new GCL proof.

Sources and claim boundaries

Maintained Erdős #705, https://www.erdosproblems.com/705 ; https://github.com/google-deepmind/formal-conjectures/blob/85f863718beeec7b58a3a1926ee92e3472bc2020/FormalConjectures/ErdosProblems/705.lean ; O'Donnell [OD99] thesis full proof uninspected. Authenticated source-return evidence. Historical full proofs not independently replayed. no new independent primary theorem certification, public mathematics rendering or V2 admission.

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

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