Petersen Coloring Conjecture
Jaeger conjectured that every bridgeless cubic graph admits a Petersen coloring: a map into the edges of the Petersen graph such that, for every vertex of , the three edges at are sent to three edges meeting at a common vertex of . Equivalently, by Jaeger's theorem, 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. False: there is an explicit simple connected bridgeless cubic graph on vertices, of girth five and edge- and vertex-connectivity three, with no Petersen coloring.
- Result
- Disproved(see note)
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Graph theory
- Posed by
- François Jaeger
- Year posed
- 1985
- Years open
- 41y
- Solved
- 2026-08-08
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Bryce Putman
- Verification
- Site-confirmed
- Publication
- Preprint
- Significance
- 40 / 100
- Disclosed cost
- —
- Wikipedia
- Not counted (article postdates the solution)
What was actually shown
The implication runs one way: the Petersen coloring conjecture implies Berge-Fulkerson and the 5-cycle-double-cover conjecture, so refuting it leaves both of those open. The paper does not claim 112 is minimum, and it supplies a second, nonisomorphic D3-symmetric 112-vertex counterexample. Combined with a theorem of Ma, Mattiolo, Steffen and Wolf, one counterexample yields infinitely many.
What the AI did
The paper's "Computational provenance and responsibility" section states in full: "OpenAI language-model systems were used extensively in the discovery, computational search, verification, and preparation of this work. The author reviewed the final claims and artifacts and accepts responsibility for the contents." No product name, model version or division of labour is given, so which of discovery, search, verification and write-up the model actually carried is not recoverable from the paper. The catalog records the model as ChatGPT because that is this catalog's convention for an unnamed OpenAI system; the paper itself names none.
Verification
Reproduced by this site on 12 August 2026, independently of the paper's certificates. The 112-vertex graph was rebuilt from the edge table in the paper's own appendix, and the SHA-256 digest of its normalized sorted edge list reproduces the digest in Theorem 1.1 exactly, which pins the object under review to the one the paper claims. Every property in that theorem re-derived here: 112 vertices, 168 edges, simple, cubic, connected, bridgeless, girth five, edge-connectivity three, vertex-connectivity three. Non-existence of a Petersen coloring was then re-proved with a CNF encoding written here from the definition - each edge carries one of the 15 edges of the Kneser graph KG(5,2), each vertex selects one of the 10 target stars, the three edges at a vertex land in that star and are pairwise distinct - and solved with CaDiCaL via PySAT. The result is UNSAT, so no Petersen coloring exists. This is a different route from the paper's: it re-derives the unsatisfiability rather than replaying the shipped DRAT certificates, and the encoding was written without reference to the paper's encoder. It arrives at the same 3640 variables, which is forced by the problem shape, but at 31,360 clauses against the paper's 68,324, so the two are genuinely different formulations of the same question rather than the same one twice. The solve took about nine minutes, and was run twice in separate processes with identical results. The controls matter as much as the result. K4, K3,3, the 3-cube, the prism, the Desargues graph and the Petersen graph itself were all put through the same encoder and all came back satisfiable. The Petersen graph control is the important one, since it is a snark, so a coloring found for it rules out the encoder having quietly tested 3-edge-colorability instead. As a further consistency check the graph was confirmed not 3-edge-colorable, which it must not be: every 3-edge-colorable cubic graph has a Petersen coloring, so any counterexample has to be a snark. What has not been checked here: the second, D3-symmetric counterexample H, the normal-5-edge-coloring formulation (equivalent by Jaeger's theorem, which the paper proves), and the shipped DRAT proofs themselves. arXiv preprint, four days old at review, not peer-reviewed and with no independent expert commentary yet.
Sources
Submitted by VibeGene on