A counterexample to Erdős problem 108 via arc graphs

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

For every positive integer MM, we construct a finite triangle-free graph GG of chromatic number at least MM in which every ordinary four-cycle-free subgraph is 6-colorable. Consequently, no chromatic threshold forces a subgraph of girth at least five and chromatic number at least seven, which gives a negative answer to Erdős problem 108. The proof uses a multipartite random graph of bounded acyclic outdegree in which every subgraph under a prescribed degree cap is 4-colorable. An arc-graph construction raises the host chromatic number while partitioning each four-cycle-free subgraph into a part controlled by the degree cap and a forest. The linked Lean verification covers the original negative answer. The written proof includes the triangle-free strengthening.

Author comments: TeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000120. Pinned original manuscript, formal source and verification records are listed at https://github.com/TheJustinSunPrize/awards/pull/4903

Provenance statement

The manuscript discloses substantial ChatGPT and Codex assistance. This TeX edition preserves the mathematical proof and corrects the verification scope stated in the original abstract and Lean table.

References

  1. T. F. Bloom, Erdős Problem #108 (https://www.erdosproblems.com/108), Erdős Problems.link
  2. Google DeepMind and contributors, Formal Conjectures, file FormalConjectures/ErdosProblems/108.lean , repository (https://github.com/google-deepmind/formal-conjectures). The task revision is specified in Section 5.link
  3. B. Janzer, R. Steiner and B. Sudakov, Chromatic number and regular subgraphs, Bull. London Math. Soc. (2026), DOI (https://doi.org/10.1112/blms.70262), preprint arXiv:2410.02437 (https://arxiv.org/abs/2410.02437).arXivDOI
  4. Lean community, The Lean 4 theorem prover, version 4.33.1 (https://github.com/leanprover/lean4/releases/tag/v4.33.1).link
  5. Pinned original-source edition (https://github.com/JENW1N/complete-math-solutions/blob/a624e9de77e0bd8868e7103f8b379f9dbd86b607/Solutions/Erdos108.lean) and verification report (https://github.com/JENW1N/complete-math-solutions/blob/a624e9de77e0bd8868e7103f8b379f9dbd86b607/verification/erdos108.json).link
  6. Conjectures.io, Erdős problem 108, production verification record (https://conjectures.io/results/8c083793-9c3c-4960-8a23-869e54fcb584).link
  7. J. Kohlmeyer and L. Kruer, Original arc-graph manuscript (https://github.com/lkruer/conjectures/blob/e88dec4c88e42824b4acd3f9559febe67115471b/problems/erdos-108/paper/proof.pdf), September 15, 2026, linked from Justin Sun Prize submission JSP-000120 (https://github.com/TheJustinSunPrize/awards/pull/4903).link
  8. Source notes on manuscript correspondence (https://github.com/lkruer/conjectures/blob/e88dec4c88e42824b4acd3f9559febe67115471b/problems/erdos-108/lean/README.md#manuscript-correspondence), pinned at the manuscript revision.link

Version history

  1. v1 · 7 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000120. Pinned original manuscript, formal source and verification records are listed at https://github.com/TheJustinSunPrize/awards/pull/4903CurrentNov 21, 2026