Berge-Fulkerson Covers, Cycle Double Covers, Flows and Exact Normality Defects of the First Counterexamples to the Petersen Coloring Conjecture

Abstract

Jaeger's Petersen coloring conjecture (1988), which asserted that every bridgeless cubic graph admits an edge map onto the Petersen graph sending every vertex star onto a vertex star, was refuted in August 2026: Putman exhibited two nonisomorphic 112-vertex counterexamples with SAT-solver certificates, Jooken gave a human-checkable proof, and Goedgebeur, Jooken, Máčajová, Mattiolo, Mazzuoccolo and Ulyanov found two 52-vertex counterexamples and infinite families, placing the order of a smallest counterexample between 40 and 52. The conjecture had been the strongest known sufficient condition for the Berge-Fulkerson conjecture and the 5-cycle double cover conjecture. We determine, by exact proof-carrying computation, what survives on the five retrievable counterexamples (orders 52, 52, 68, 112, 112). Independent encodings refute Petersen colorings and normal 5-edge-colorings of all five graphs with proofs checked by drat-trim. Every one of the five graphs admits a Berge-Fulkerson cover, a Berge cover by five perfect matchings, a Fan-Raspaud triple, a 5-cycle double cover and a nowhere-zero 5-flow, all given as explicit witnesses re-verified from the graph alone; none admits a nowhere-zero 4-flow. Their perfect matching index is exactly 4, one below the Petersen graph's value. The two 112-vertex graphs have oddness 4 and resistance 3, whereas the other three have oddness 2 and resistance 2, every value certified from both sides. All five admit normal and strong normal 6-edge-colorings, so their normal chromatic index is exactly 6. Defining the Petersen defect as the least number of vertices at which the star condition must fail, we prove that for any edge map into the Petersen graph the number of bad vertices is never exactly one, and we find that all five graphs have defect exactly 2 with every vertex pair critical (17,362 explicit witnesses). The defect is at most the least number of abnormal edges of a proper 5-edge-coloring, and both equal 2 on the five graphs. Neither is bounded: rings of t counterexamples joined through 2-edge cuts, and cubic frames whose vertices are replaced by counterexamples minus a vertex, need one bad vertex in every block, with equality on the instances computed. Consequently no sublinear function bounds the number of abnormal edges on 2-connected or on 3-connected cubic graphs, so four of the five statements whose equivalence was conjectured by Mattiolo, Mazzuoccolo and Mkrtchyan are false, and the conjectured equivalence reduces to one question on cyclically 4-edge-connected cubic graphs, for which a single graph of Petersen defect at least 3 would suffice. Finally, no counterexample consists solely of copies of the Petersen 4-pole F from which all known counterexamples are built. All computations are propositional with checked DRAT certificates or explicit witnesses. The paper decides nothing about the general covering and flow conjectures. Source code, data, computational records and verification instructions: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/combinatorics/petersen-coloring).