Petersen Coloring Conjecture
Statement
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.
Context
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.
Jaeger's conjecture is one of the central conjectures on cubic graphs: the Open Problem Garden entry calls it an extraordinary conjecture, and it implies both the Berge-Fulkerson conjecture and the 5-cycle-double-cover conjecture, with a substantial literature on normal edge-colorings and sublinear approximations built around it. Placed above a well-tracked specialist conjecture and below the cycle double cover conjecture itself (55), which is more widely known outside the area.
People
Attempts
No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
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.
Reviews
1 machine checkNo person has reviewed this attempt. 1 machine check below — a machine check is not human verification.
Machine check · not human verification
machine: correctscope Reproduction by the VibeMathed site
Reproduced here on 12 August 2026, independently of the paper's certificates. The 112-vertex graph was rebuilt from the appendix edge table, and the SHA-256 of its normalized sorted edge list reproduces the digest in Theorem 1.1 exactly, pinning the object under review to the one claimed. Every property in that theorem was rederived: 112 vertices, 168 edges, simple, cubic, connected, bridgeless, girth five, 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 , 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. UNSAT. That re-derives the unsatisfiability rather than replaying the shipped DRAT certificates, and the encoder was written without reference to the paper's: the same 3640 variables, forced by the problem shape, but 31,360 clauses against their 68,324. It ran twice in separate processes with identical results. Six controls - , , the 3-cube, the prism, Desargues and the Petersen graph itself - all came back satisfiable through the same encoder. Petersen is the important one, being a snark: a coloring for it rules out the encoder having quietly tested 3-edge-colorability. Not checked: the second -symmetric counterexample, the normal-5-edge-coloring formulation, and the DRAT proofs. Four-day-old arXiv preprint, unrefereed.
No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.
Discussion of this attempt
no comments
Solve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.
Discussion
Nothing has been said about this problem yet.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.