A 112-Vertex Counterexample to the Petersen Coloring Conjecture

Abstract

We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pole F and one copy of C, where F is obtained from the Petersen graph by deleting the endpoints of one edge. We give direct SAT formulations for Petersen colorings and normal 5-edge-colorings. CaDiCaL 3.0.1 returned UNSAT for both formulas, and drat-trim verified the resulting DRAT proofs. The ancillary archive contains the construction, an explicit relabeling, the encoders, certificates, hashes, and verification programs. Combined with a theorem of Ma, Mattiolo, Steffen, and Wolf, the counterexample also implies that infinitely many connected simple bridgeless cubic graphs have no Petersen coloring. We also give a separately verified, nonisomorphic $D_3$-symmetric 112-vertex counterexample. We do not address whether 112 is minimum.

Disclosure

“raph–encoding pair has its own CNF and checked DRAT proof. The ancillary documentation lists the relevant files and reproduction steps, and the compact archive has its own SHA-256 manifest. Computational provenance and responsibility 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.”

PDF page 8

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T05:00:59.090432Z

Structural counts