Petersen Coloring Conjecture

Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring: a map $\varphi\colon E(G)\to E(P)$ into the edges of the Petersen graph $P$ such that, for every vertex $v$ of $G$, the three edges at $v$ are sent to three edges meeting at a common vertex of $P$. 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 $112$ vertices, of girth five and edge- and vertex-connectivity three, with no Petersen coloring.

This preprint was not the first disproof. A 68-vertex counterexample was posted to X on 23 July 2026 by @NeuralReformist, credited to GPT-5.6 Sol Ultra, sixteen days earlier. This site decoded that sparse6 string and checked it independently: 68 vertices, 102 edges, simple, cubic, connected, bridgeless, girth five, and no Petersen coloring under the same encoder used for the 112-vertex graph. Whether the two are independent is unknown - the preprint does not cite the post. The headline axes still record the preprint, the only complete writeup with certificates. 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 $D_3$-symmetric 112-vertex counterexample. Combined with a theorem of Ma, Mattiolo, Steffen and Wolf, one counterexample yields infinitely many.