Vertex-critical four-chromatic graphs with no small critical edge set

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

Contributed by Liam Kruer ↗, Jensen Kohlmeyer

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

For every positive integer rr, we construct a finite four-chromatic graph such that deleting any vertex lowers the chromatic number, and deleting any set of at most rr 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.

Author comments: TeX 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/5110

Provenance statement

The manuscript credits OpenAI Codex with mathematical exploration, computational checks, Lean proof development and drafting. This TeX edition preserves the original four-color proof and links the cited higher-color result and the pinned finite-existence verification.

References

  1. E. Skottová and R. Steiner, Critical edge sets in vertex-critical graphs , preprint, arXiv:2508.08703 (2025), https://arxiv.org/abs/2508.08703.arXiv
  2. The Formal Conjectures Authors, Formal Conjectures , FormalConjectures/ErdosProblems/944.lean , https://github.com/google-deepmind/formal-conjectures.link
  3. Conjectures.io, Erdős 944 formalized challenge , https://conjectures.io/problems/erdos944-erdos-944/challenge?mode=formalized, accessed September 10, 2026.link
  4. The mathlib Community, mathlib4 , https://github.com/leanprover-community/mathlib4.link

Version history

  1. 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