Appendix 8.6 — the graph is uncolourable
ProvedSnarkGen.Zhang.g1_not_colourablecounterexampleedge-colouringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1snarks
Let be the first graph of Appendix 8.6 (34 vertices, 51 edges, paper vertex renamed ). Then is uncolourable: there is no map
giving distinct colours to any two distinct edges that share an endpoint. In other words, the chromatic index of is .
Uncolourability is the defining property of a snark and the hardest to certify by hand.
Formalization Note "Colourable" is G.lineGraph.Colorable 3, a proper -colouring of the line graph.
Preamble
import Mathlib import Definitions.Def_SnarkGen_Zhang_g1 import Definitions.Def_SnarkGen_EdgeInsertion_Colourable
Formal statement
namespace SnarkGen.Zhang theorem g1_not_colourable : ¬ SnarkGen.EdgeInsertion.Colourable g1 := by sorry end SnarkGen.Zhang
Source
G. Brinkmann, J. Goedgebeur, J. Hägglund, K. Markström, Generation and properties of snarks, arXiv:1206.6690v3, p. 36, Appendix 8.6 (heading and first list); p. 4, Section 2 (definition of snark)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.