Appendix 8.1 — the graph is uncolourable
ProvedSnarkGen.OddFactors.g81_not_colourablecounterexampleedge-colouringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1snarks
Let be the 26-vertex graph of Appendix 8.1. Then is uncolourable: its edges admit no proper 3-colouring,
Uncolourability is the defining property of a snark (Section 2), and must have it to be a counterexample to Conjecture 4.11.
Formalization Note "Colourable" means that the line graph of is vertex 3-colourable.
Preamble
import Mathlib import Definitions.Def_SnarkGen_OddFactors_Snark import Definitions.Def_SnarkGen_OddFactors_G81
Formal statement
namespace SnarkGen.OddFactors /-- The graph `G₈.₁` of Appendix 8.1 (arXiv:1206.6690v3, p. 29) is uncolourable: its edges admit no proper 3-colouring. -/ theorem g81_not_colourable : ¬ SnarkGen.EdgeInsertion.Colourable G81 := by sorry end SnarkGen.OddFactors
Source
G. Brinkmann, J. Goedgebeur, J. Hägglund, K. Markström, Generation and properties of snarks, arXiv:1206.6690v3, p. 4, Section 2 (snark); p. 11, Observation 4.12; p. 29, Appendix 8.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.