A 52-vertex graph tightens the Petersen Coloring Conjecture counterexample

← Back to the filtered Breakthrough Tracker

Stable ID

math-petersen-coloring-counterexample-2026

Revision

math-petersen-coloring-counterexample-2026.v2

Field

Mathematics · Graph theory and computer-assisted proof

Evidence

Tier 1 · Peer reviewed: No

Record state

Provisional · Counterexample independently corroborated

Last checked

2026-09-01

AI role

Putman reports extensive OpenAI-model use in discovery, computational search, verification and preparation. Jooken reports GPT-5.6 Sol assistance with presentation and proof rewriting while stating that he independently verified every mathematical statement and proof. The 52-vertex follow-up does not disclose a substantive AI role.

Record details

Problem or result

Jaeger’s Petersen Coloring Conjecture for bridgeless cubic graphs

Authors

Bryce Putman; independent proof by Jorik Jooken; 52-vertex refinement by Jan Goedgebeur, Jorik Jooken, Edita Máčajová, Davide Mattiolo and Giuseppe Mazzuoccolo

Institutions

Leiden University; KU Leuven; Ghent University; Comenius University; University of Modena and Reggio Emilia

Result date

112-vertex manuscripts August 8–14; 52-vertex manuscript deposited August 14, 2026

Why it matters

The 112-vertex construction refuted the conjecture and was independently checked. The new explicit graph cuts the smallest-known upper bound to 52 vertices, while prior exhaustive work leaves a 38-vertex lower bound.

Limits

The 52-vertex manuscript is an unrefereed first version. It prints an explicit edge list and a construction argument but does not provide a separate machine-checkable certificate, and no independent verification of that smaller graph was located. The exact minimum remains between 38 and 52 vertices.

Sources

1. Primary: Bryce Putman, 112-vertex Petersen-coloring counterexample
2. Artifacts: Frozen graph, SAT, DRAT and verification artifacts
3. Independent: Jorik Jooken, human-checkable proof of the 112-vertex counterexample
4. Primary: Goedgebeur et al., 52-vertex counterexample and infinite family

Correction and revision history

1. 2026-08-22 — Added after primary-source, scope, status, AI-role and limitation review.
2. 2026-09-01 — Added the presented 52-vertex counterexample and infinite cyclically four-edge-connected family; the smaller graph remains independently unchecked.

Machine-readable: JSON v1 · CSV v1 · Schema v1

This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.