A distinct symmetric 112-vertex counterexample

Statement

There is a simple connected bridgeless cubic graph H on 112 vertices and 168 edges, of girth five and both connectivities three, with no Petersen coloring or normal five-edge-coloring; H is nonisomorphic to G and has automorphism group D₃ of order six.

Assumptions

The Section 6 graph is separately encoded and certified; it is not a relabeling of the main graph.

Explanation

Constructions · 1

Inspect the symmetric graph

Inspect the exact adjacency

112 numbered vertices and 168 undirected edges.

Vertex

Vertex 0 has neighbors 1, 5, 31.

Complete adjacency table

Every numbered vertex and its neighbors
Vertex	Neighbors
0	1, 5, 31
1	0, 2, 6
2	1, 7, 52
3	5, 6, 11
4	6, 7, 9
5	0, 3, 7
6	1, 3, 4
7	2, 4, 5
8	9, 10, 11
9	4, 8, 14
10	8, 12, 20
11	3, 8, 28
12	10, 13, 17
13	12, 14, 18
14	9, 13, 19
15	17, 18, 22
16	18, 19, 74
17	12, 15, 19
18	13, 15, 16
19	14, 16, 17
20	10, 21, 25
21	20, 22, 26
22	15, 21, 27
23	25, 26, 30
24	26, 27, 109
25	20, 23, 27
26	21, 23, 24
27	22, 24, 25
28	11, 29, 33
29	28, 30, 34
30	23, 29, 35
31	0, 33, 34
32	34, 35, 111
33	28, 31, 35
34	29, 31, 32
35	30, 32, 33
36	37, 41, 67
37	36, 38, 42
38	37, 43, 88
39	41, 42, 47
40	42, 43, 45
41	36, 39, 43
42	37, 39, 40
43	38, 40, 41
44	45, 46, 47
45	40, 44, 50
46	44, 48, 56
47	39, 44, 64
48	46, 49, 53
49	48, 50, 54
50	45, 49, 55
51	53, 54, 58
52	2, 54, 55
53	48, 51, 55
54	49, 51, 52
55	50, 52, 53
56	46, 57, 61
57	56, 58, 62
58	51, 57, 63
59	61, 62, 66
60	62, 63, 110
61	56, 59, 63
62	57, 59, 60
63	58, 60, 61
64	47, 65, 69
65	64, 66, 70
66	59, 65, 71
67	36, 69, 70
68	70, 71, 109
69	64, 67, 71
70	65, 67, 68
71	66, 68, 69
72	73, 77, 103
73	72, 74, 78
74	16, 73, 79
75	77, 78, 83
76	78, 79, 81
77	72, 75, 79
78	73, 75, 76
79	74, 76, 77
80	81, 82, 83
81	76, 80, 86
82	80, 84, 92
83	75, 80, 100
84	82, 85, 89
85	84, 86, 90
86	81, 85, 91
87	89, 90, 94
88	38, 90, 91
89	84, 87, 91
90	85, 87, 88
91	86, 88, 89
92	82, 93, 97
93	92, 94, 98
94	87, 93, 99
95	97, 98, 102
96	98, 99, 111
97	92, 95, 99
98	93, 95, 96
99	94, 96, 97
100	83, 101, 105
101	100, 102, 106
102	95, 101, 107
103	72, 105, 106
104	106, 107, 110
105	100, 103, 107
106	101, 103, 104
107	102, 104, 105
108	109, 110, 111
109	24, 68, 108
110	60, 104, 108
111	32, 96, 108

Construction details

Order and size: 112 vertices; 168 edges
Coloring encodings: Petersen: 3,640 variables and 68,324 clauses; normal five: 1,960 variables and 25,484 clauses
Certificate tools: CaDiCaL 3.0.1 at c60730422e758ef1cebe7aeddf2dda31c996bf04; drat-trim at 2e3b2dc0ecf938addbd779d42877b6ed69d9a985
Normalized edge-list SHA-256: 0f2d8858110c6f012de7ddffa92fdbc709d7da630f199b0e3c81bb56eb6b35c7

The exact adjacency data identifies this witness. Inspecting neighbors does not verify noncolorability, and 112 is not asserted to be minimal.

A distinct symmetric 112-vertex counterexample →

Evidence

Source reports

Proved

External SAT and DRAT checks reported ↗

Four graph/formulation pairs; not an OpenMath execution.

Petersen counterexample: frozen construction and certificates · 03_CERTIFICATION, 04_OPTIONAL_D3 and 05_DOCUMENTATION →

Source dated Aug 8, 2026 · Observed Oct 14, 2026

Proved

Second nonisomorphic counterexample reported ↗

Exact D₃-symmetric graph in Theorem 6.1.

A 112-Vertex Counterexample to the Petersen Coloring Conjecture · Theorem 6.1; Section 6 →

Source dated Aug 8, 2026 · Observed Oct 14, 2026

Connections

In this problem · publication v7

Petersen coloring conjecture →

Counterexample · Proved

Relationship not independently reviewed. This concerns its use in this problem.

Sources

A 112-Vertex Counterexample to the Petersen Coloring Conjecture →

Theorem 6.1; Section 6 → · Original passage ↗
Recorded wording
A second, nonisomorphic 112-vertex graph has automorphism group D₃ of order six and separately checked coloring certificates.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.

Bryce Putman · Preprint · Publication date Aug 8, 2026

Source-reported results and external checks are separate from independent OpenMath assessment.

Revision & attribution

Source revision: v1. Observed Oct 14, 2026.

Putman reports extensive OpenAI-model assistance in discovery, search, verification and preparation; he reviewed the final claims and artifacts and accepts responsibility.

Petersen counterexample: frozen construction and certificates →

03_CERTIFICATION, 04_OPTIONAL_D3 and 05_DOCUMENTATION → · Original passage ↗
Recorded wording
CaDiCaL 3.0.1 reports UNSAT; drat-trim reports VERIFIED for four DRAT proofs. Separate encoders, satisfiable controls and status-parsing negative controls support the reported checks.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.

Bryce Putman · Project documentation · Publication date Aug 8, 2026

Source-reported results and external checks are separate from independent OpenMath assessment.

Revision & attribution

Source revision: 1.1.0. Observed Oct 14, 2026.

The author attributes discovery and verification assistance to OpenAI systems; source logs are external computational reports.

History

Statement versions

Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.

Assessment history · 2

Assessments retained in these publication records. Earlier statement versions retain their own source histories.

Proved

Second nonisomorphic counterexample reported ↗

Exact D₃-symmetric graph in Theorem 6.1.

Source dated Aug 8, 2026 · Observed Oct 14, 2026 · Source passage →

Proved

External SAT and DRAT checks reported ↗

Four graph/formulation pairs; not an OpenMath execution.

Source dated Aug 8, 2026 · Observed Oct 14, 2026 · Source passage →

Record details

Claim ID: claim-petersen-112-symmetric-witness
Statement version: 1
SHA-256: c7fdc21883fb9a383b73864954056882927d247d0375179e220d52c5c4a7a49c

Publication records

Petersen coloring conjecture · publication v7 · JSON →