REVIEW 2 major objections 4 minor
A human-checkable proof of the 112-vertex counterexample to the Petersen coloring conjecture
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A short, hand-checkable proof confirms the 112-vertex counterexample to the Petersen coloring conjecture.
desk verdict A genuinely human-checkable proof of Putman's 112-vertex Petersen-coloring counterexample, with one load-bearing finite table that should be independently verified before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the 4-pole F, obtained by deleting two adjacent vertices from the Petersen graph P and leaving four semi-edges; Lemma 2.1 classifies how a P-coloring of F can assign edge labels to those semi-edges, with the relation R(g,h) encoding allowed output pairs depending on whether the input labels are at distance 0, 1, 2, or 3 in the line graph Q = L(P). The 4-pole L, made from four copies of F joined to a claw, then has the forced behavior described in Lemma 2.2: its output semi-edges are determined by its input semi-edges up to a small list. The final contradiction is structural: the constraints from three L-copies force four edges of P to be pairwise adjacent, but Q has no 4-clique.
What would settle it
Exhibit a Petersen coloring of G — a consistent assignment of each edge of G to an edge of the Petersen graph and each vertex to a vertex such that incident triples map to incident triples; a single such assignment disproves Theorem 2.3.
Extended reading notes
Core claim
The central discovery is Theorem 2.3: there exists a cubic bridgeless graph G on 112 vertices that admits no P-coloring, meaning no total map taking edges of G to edges of the Petersen graph P and vertices of G to vertices of P so that each vertex's incident edges map to the three edges incident with a single vertex of P. The proof establishes this by first classifying the P-coloring behavior of the 4-pole F (P with two adjacent vertices removed) through a 64-case enumeration, then showing that a 36-vertex 4-pole L built from four copies of F has the forcing behavior described in Lemma 2.2. Three copies of L are wired together with a claw to form G; applying Lemma 2.2 forces four edges of P to be pairwise adjacent in the line graph Q = L(P), which is impossible because Q has no 4-clique. The proof is fully finite and does not rely on a SAT solver.
Load-bearing premise
The entire proof leans on the correctness and completeness of the 64-row table in the appendix: if any of the 55 rows marked with a dash actually extends to a Petersen coloring of the 4-pole F, then the gadget lemmas and the final contradiction no longer follow.
Editorial extensions
If this is right
- The Petersen coloring conjecture is false: not every bridgeless cubic graph admits a Petersen coloring.
- The 112-vertex graph's status as a counterexample no longer rests on a SAT computation; its non-colorability is established by a finite case analysis.
- The implication chain from the Petersen coloring conjecture to the Berge-Fulkerson conjecture and the 5-cycle double cover conjecture is no longer available; those conjectures remain open and need independent approaches.
- The 4-pole gadgets F and L, with their classified coloring behaviors, are reusable building blocks for constructing and testing other cubic graphs for Petersen colorability.
- Any graph assembled to force four edge labels to be pairwise adjacent in the line graph of the Petersen graph will be non-P-colorable in the same way.
Reading between the lines
- The same gadget structure might yield smaller counterexamples: since the proof only uses the forced adjacency pattern at the end, one could search over graphs assembled from L-copies to minimize vertex count.
- The proof suggests a sufficient condition for non-P-colorability: a bridgeless cubic graph whose P-coloring constraints force four edges of the Petersen graph to be pairwise adjacent contradicts the clique number of the line graph, so any such constructed graph is a counterexample.
- The table-driven method could be partially mechanized at a much smaller scale: checking the 64 cases of Lemma 2.1 is a task a reader can do by hand, and the same template could generate proofs for larger gadgets.
- If future work finds a smaller counterexample, this proof provides the template: isolate a small multipole whose colorings are finitely classifiable, combine them, and reduce the contradiction to a known structural property of the target graph.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper provides a hand-checkable proof that the 112-vertex cubic bridgeless graph recently proposed by Putman is a counterexample to Jaeger's Petersen coloring conjecture. The proof first analyzes P-colorings of a 4-pole F obtained by deleting two adjacent vertices from the Petersen graph, encoding the outcome in a 64-row table (Lemma 2.1). It then derives transfer relations for a 36-vertex 4-pole L built from four copies of F (Lemma 2.2). Three copies of L are joined to a claw to form the 112-vertex graph G; assuming a P-coloring of G, the paper derives that four edges of the Petersen graph must be pairwise adjacent in its line graph Q, contradicting the fact that Q has no K4. The final contradiction is short and structural, and the proof does not rely on a SAT solver.
Significance. If the proof is correct, this paper gives the first counterexample to a longstanding conjecture and, more importantly, explains the counterexample through reusable multipole behavior rather than a large SAT computation. The final argument using the clique number of the line graph of the Petersen graph is elegant, and the reduction to small finite cases is a genuine methodological contribution. The proof has no fitted parameters and does not assume non-colorability of the target graph. The main caveat is that the load-bearing finite enumeration in Lemma 2.1 is not fully exhibited; the contribution is therefore conditional on completing that verification.
major comments (2)
- [§2, Lemma 2.1 and Table 1] The entire proof hinges on the assertion that, after fixing σ(12)=e1, σ(24)=e2, and σ(27)=e3, exactly 9 of the 64 enumerated assignments around vertex 2 extend to a P-coloring of F, and that in each of these 9 cases the extension is unique. Table 1 displays the 9 completed rows, but the 55 rows marked with dashes contain no derivation or certificate showing that no completion exists. Since equations (1)–(3), Lemma 2.2, Table 2, and Theorem 2.3 all depend on Lemma 2.1, a single hidden valid completion among those 55 rows would invalidate the main result. Please provide an explicit checkable argument for each dash row, or include a machine-verifiable certificate together with a clear explanation of how it establishes the negative cases; in its current form the table is an assertion rather than a human-checkable proof.
- [§2, Lemma 2.2 and Theorem 2.3] Lemma 2.2 states implications conditional on dist(σ(i1(L)),σ(i2(L))) being 0, 1, or in {2,3}, but it does not explicitly state that these are the only possible values for a P-coloring of L. Theorem 2.3 relies on this exhaustiveness when it enumerates only δ1,δ2 ∈ {0,1,{2,3}} in Table 2. The proof of Lemma 2.2 appears to establish exhaustiveness through the S/O case analysis, but the lemma should state it explicitly (for example, 'for every P-coloring of L, the distance is 0, 1, 2, or 3'), and the proof should flag where this is concluded. Without such a statement, the step 'the nine cases' in Theorem 2.3 is not formally justified.
minor comments (4)
- [§2, Lemma 2.1] The reduction 'by symmetry of P, without loss of generality σ(12)=e1, σ(24)=e2, σ(27)=e3' should be justified with a sentence on the ordered-star transitivity of Aut(P), so that the reader can verify that Table 1 indeed covers all possible colorings of the star at vertex 2.
- [§2, Theorem 2.3] In the sentence 'Since δ1=0, Lemma 2.2 gives σ(i1_1)=σ(i1_2)...', the equality σ(i1_1)=σ(i1_2) follows directly from the definition of δ1; Lemma 2.2 provides the distance statement dist(σ(i1_1),σ(o1_1))=1. Please rephrase to avoid attributing the equality to Lemma 2.2.
- [Abstract and Introduction] There are typographical spacing issues in 'on112vertices' and 'the4-poleF'; please insert spaces before the numbers.
- [§2, Lemma 2.2] The paragraph introducing the cases S and O is terse. The phrase 'the other endpoint in P of the label on the edge to c is used' would be clearer if S and O were defined formally as conditions on the ordered pair of labels at each leaf of the claw.
Circularity Check
No circularity: the non-P-colorability of the constructed graph is derived from local finite case analyses, not assumed as input.
full rationale
The paper's central claim, Theorem 2.3, is that a specific 112-vertex cubic bridgeless graph does not admit a Petersen coloring. The graph is constructed explicitly from four-poles and claws, and its non-colorability is proved by contradiction using Lemma 2.2, which in turn rests on Lemma 2.1 and the finite enumeration in Table 1. Nowhere does the proof assume that the graph is non-P-colorable or that the target conclusion holds. The external input is Putman's graph construction from [13], which is used as a combinatorial object, not as evidence of non-colorability. The local behavioral statements about the four-pole F are established by enumerating 64 cases; the 55 rows marked with dashes are asserted without individual derivation, but this is a verification gap, not a circular step. The R-relations (1)-(3) are direct reformulations of Lemma 2.1, and Lemma 2.2's case analysis applies them without reimporting the theorem's conclusion. The only self-citation, reference [6], is a survey cited in passing and is not load-bearing. All load-bearing steps are either explicit finite case analyses or standard structural facts about the Petersen graph and its line graph. Thus the derivation is self-contained and non-circular.
Assumptions & free parameters
assumptions (3)
- standard math Petersen graph symmetry permits fixing sigma(12)=e1, sigma(24)=e2, sigma(27)=e3 in Lemma 2.1.
- ad hoc to paper Table 1 is complete and correct: exactly 9 of the 64 enumerated assignments extend to a P-coloring of F.
- domain assumption The graph G constructed from three copies of L and a claw is cubic and bridgeless.
Cite this review
Pith. "Pith review of A human-checkable proof of the 112-vertex counterexample to the Petersen coloring conjecture." pith.science (2026). https://pith.science/paper/MDX5NKPA
@misc{pith2026260810028,
author = {Pith},
title = {Pith review of: A human-checkable proof of the 112-vertex counterexample to the Petersen coloring conjecture},
year = {2026},
howpublished = {\url{https://pith.science/paper/MDX5NKPA}},
note = {Machine review of arXiv:2608.10028}
}
abstract
The Petersen coloring conjecture of Jaeger asserts that every bridgeless cubic graph admits a Petersen coloring. Recently, Putman presented an explicit counterexample on $112$ vertices and verified its non-colorability by showing, using a SAT solver, that an instance with $3640$ variables and $68324$ clauses is unsatisfiable. We give a short human-checkable proof that this graph is indeed a counterexample. Our proof determines the coloring behavior of the multipoles used in the construction by means of small explicit finite case analyses and reduces the final contradiction to a simple structural property of the line graph of the Petersen graph. Besides providing a proof that does not rely on a large SAT computation, our approach gives further insight into the gadgets underlying the construction.
Figures
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.