Source authenticated

Petersen Coloring Conjecture

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.

Exact FrontierDelta

Prior state unknown→disproved

Scope and record

Occurred: Jul 23, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: site-confirmed. Publication: preprint. AI contribution: ai-co-developed. Editorial metadata: CC BY 4.0; linked content retains its own rights.

Canonical aliases: Petersen Coloring Conjecture · Petersen Coloring

Confidence: Not scored

Registry verification: site confirmed · preprint · resolved

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Bryce Putman
human · human collaborator

ChatGPT
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: Petersen Coloring Conjecture

specialist registry · passed

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 $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. 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 - $K_4$ , $K_{3,3}$ , 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 $D_3$ -symmetric counterexample, the normal-5-edge-coloring formulation, and the DRAT proofs. Four-day-old arXiv preprint, unrefereed.