Vertex-critical four-chromatic graphs with no small critical edge set
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
For every positive integer , we construct a finite four-chromatic graph such that deleting any vertex lowers the chromatic number, and deleting any set of at most edges preserves it. The proof combines punctured cyclic three-colorings, an integral height character, an Andrásfai winding bound, and a Chinese remainder construction with an exact classification of its small-deficit characters. Together with the higher-color result of Skottová and Steiner, this gives finite existence for every chromatic number at least four. The accompanying Lean formalization checks the finite-existence theorem.
Provenance statement
References
- E. Skottová and R. Steiner, Critical edge sets in vertex-critical graphs , preprint, arXiv:2508.08703 (2025), https://arxiv.org/abs/2508.08703.arXiv
- The Formal Conjectures Authors, Formal Conjectures , FormalConjectures/ErdosProblems/944.lean , https://github.com/google-deepmind/formal-conjectures.link
- Conjectures.io, Erdős 944 formalized challenge , https://conjectures.io/problems/erdos944-erdos-944/challenge?mode=formalized, accessed September 10, 2026.link
- The mathlib Community, mathlib4 , https://github.com/leanprover-community/mathlib4.link
Version history
- v1 · 13 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000785. Pinned source, proof audit and credit for the separate prescribed-order extension: https://github.com/TheJustinSunPrize/awards/pull/5110CurrentNov 21, 2026