A 112-vertex counterexample to the Petersen coloring conjecture
An explicit simple bridgeless cubic graph on 112 vertices admits no Petersen coloring, and hence no normal 5-edge-coloring, refuting a conjecture of Jaeger from 1985 with machine-checked UNSAT certificates.
- Lab
- Independent
- Model
- Unnamed OpenAI model
- Field
- Mathematics
- Date
- 2026-08-08
- Human collaborators
- Bryce Putman
- Problem posed
- 1985 · open 41 yrs
What was found
Jaeger conjectured in 1985 that every bridgeless cubic graph admits a Petersen coloring: a map from its edges into the edges of the Petersen graph sending the three edges at each vertex to three edges meeting at a common vertex of the Petersen graph. Equivalently, every bridgeless cubic graph has a normal 5-edge-coloring. The conjecture implies both the Berge–Fulkerson conjecture and the 5-cycle-double-cover conjecture. This paper gives an explicit simple connected bridgeless cubic graph on 112 vertices, of girth five and edge and vertex connectivity three, with no such coloring; the graph is pinned by a SHA-256 digest in the theorem statement itself. Non-existence is established by direct SAT formulations, with CaDiCaL 3.0.1 returning UNSAT and drat-trim verifying the resulting DRAT proofs. A second, non-isomorphic counterexample of the same order is supplied. The implication runs one way, so Berge–Fulkerson and the 5-cycle-double-cover conjecture stay open; combined with a theorem of Ma, Mattiolo, Steffen and Wolf, one counterexample yields infinitely many.
Novelty check
The Petersen coloring conjecture is tracked as open in the Open Problem Garden, whose entry calls it an extraordinary conjecture, and it carries a substantial literature on normal edge-colorings and sublinear approximations built on the assumption that it holds. No prior counterexample appears anywhere in that literature. The construction is a new concrete graph, not a retrieval of an existing example.
Caveats and known objections
A preprint, not peer-reviewed. The paper's computational provenance section states only that OpenAI language-model systems were used extensively in the discovery, computational search, verification and preparation of the work, and names no product, version or division of labour, so the model field records an unnamed OpenAI system and autonomy is graded ai-assisted, the weakest reading the disclosure permits. The paper does not claim 112 is the minimum order for a counterexample.
Independent checks
vibemathed.com curator reproduction: rebuilt the 112-vertex graph from the appendix edge table with a SHA-256 matching Theorem 1.1, rederived every property claimed there, and re-proved non-existence with an independently written CNF encoder solved by CaDiCaL rather than by replaying the shipped certificates; six control graphs including the Petersen graph itself came back satisfiable through the same encoder · link ↗
Disagree with these grades?
Bring a citation: a grade moves on evidence, not on argument.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Formally verified and AI-assisted.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded formally verified for verification and ai-assisted for autonomy. What these mean.
Cite this entry
whataifound.org. (2026). A 112-vertex counterexample to the Petersen coloring conjecture. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-08-08-petersen-coloringBibTeX
@misc{whataifound-independent-2026-coloring,
title = {A 112-vertex counterexample to the Petersen coloring conjecture},
author = {{whataifound.org}},
year = {2026},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Independent. Verification: Formally verified. Autonomy: AI-assisted.},
url = {https://whataifound.org/finding/2026-08-08-petersen-coloring}
}