A counterexample to Erdős problem 108 via arc graphs
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
For every positive integer , we construct a finite triangle-free graph of chromatic number at least 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.
Provenance statement
References
- T. F. Bloom, Erdős Problem #108 (https://www.erdosproblems.com/108), Erdős Problems.link
- 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
- 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
- Lean community, The Lean 4 theorem prover, version 4.33.1 (https://github.com/leanprover/lean4/releases/tag/v4.33.1).link
- 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
- Conjectures.io, Erdős problem 108, production verification record (https://conjectures.io/results/8c083793-9c3c-4960-8a23-869e54fcb584).link
- 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
- 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
- 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