Appendix 8.6 — the graph is a permutation graph
ProvedSnarkGen.Zhang.g1_isPermutationGraphcounterexamplep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1permutation-graphssnarks
Let be the first graph of Appendix 8.6 (34 vertices, paper vertex renamed ). Then is a permutation graph: it is cubic, and its vertex set splits into two sets and such that the induced subgraphs
are both cycles (connected and -regular). Equivalently, has a -factor consisting of two induced cycles; since has vertices, both are -cycles.
Preamble
import Mathlib import Definitions.Def_SnarkGen_Zhang_g1 import Definitions.Def_SnarkGen_Zhang_IsPermutationGraph
Formal statement
namespace SnarkGen.Zhang theorem g1_isPermutationGraph : IsPermutationGraph 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. 8, Section 4.2 (definition of permutation graph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.