Appendix 8.6 — the graph has girth at least 5
ProvedSnarkGen.Zhang.g1_five_le_egirthcounterexamplecubic-graphsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1snarks
Let be the first graph of Appendix 8.6 (34 vertices, paper vertex renamed ). The girth of a graph is the number of vertices in a shortest cycle. Then has no cycle of length or :
Girth at least is one of the defining conditions of a snark.
Formalization Note The girth is Mathlib's extended girth egirth, which is for an acyclic graph; the statement 5 ≤ g1.egirth says every cycle has length at least .
Preamble
import Mathlib import Definitions.Def_SnarkGen_Zhang_g1
Formal statement
namespace SnarkGen.Zhang theorem g1_five_le_egirth : 5 ≤ g1.egirth := 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 girth and of snark)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.