simple_graph_cycle_power_six_one_sanity
Sanity check: in C_6 (the first power of the 6-cycle), vertices 0 and 5 are adjacent (they wrap around) and 0 and 2 are not.
Statement
theorem simple_graph_cycle_power_six_one_sanity :
(simple_graph_cycle_power 6 1).Adj 0 5 ∧ ¬ (simple_graph_cycle_power 6 1).Adj 0 2- Source
- Sanity lemma for the cycle power, arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs).
- Verified
- 17 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
The proof, explained
The theorem verifies that in the cycle graph $C_6$ (modeled as the first power of the $6$-cycle on $\mathbb{Z}/6\mathbb{Z}$), vertex $0$ is adjacent to $5$ but not to $2$. By definition, two vertices $u, v \in \mathbb{Z}/6\mathbb{Z}$ are adjacent if $u \neq v$ and their cyclic distance $\min((u-v)\text{.val}, (v-u)\text{.val})$ is at most $1$. The proof unfolds this adjacency definition into explicit modular arithmetic inequalities and discharges them by finite computation.
The goal reduces to checking explicit cyclic distance inequalities in $\mathbb{Z}/6\mathbb{Z}$ for the vertex pairs $(0, 5)$ and $(0, 2)$.
By definition of `simple_graph_cycle_power`, two vertices $u, v \in \mathbb{Z}/6\mathbb{Z}$ are adjacent if and only if $u \ne v$ and their cyclic distance $\min((u - v)\text{.val}, (v - u)\text{.val})$ is at most $1$. Stating this expanded form with `show` unfolds the adjacency predicate into concrete arithmetic inequalities on $\mathbb{Z}/6\mathbb{Z}$.
show ((0 : ZMod 6) ≠ 5 ∧ _) ∧ ¬ ((0 : ZMod 6) ≠ 2 ∧ _)Vertices $0$ and $5$ are adjacent, while $0$ and $2$ are not adjacent. automation
The goal is closed by the `decide` tactic via finite evaluation in $\mathbb{Z}/6\mathbb{Z}$. For $0$ and $5$, $(0 - 5)\text{.val} = 1$ and $(5 - 0)\text{.val} = 5$, so the cyclic distance is $\min(1, 5) = 1 \le 1$, meaning $0$ and $5$ are adjacent. For $0$ and $2$, $(0 - 2)\text{.val} = 4$ and $(2 - 0)\text{.val} = 2$, so the cyclic distance is $\min(4, 2) = 2 \not\le 1$, meaning $0$ and $2$ are not adjacent.
decide
- The `show` command on line 3 is a formal detail: it manually unfolds the definition of adjacency in `simple_graph_cycle_power` so that Lean's typeclass resolution can recognize the goal as a decidable proposition on `ZMod 6` and `ℕ`, which `decide` on line 4 can then compute.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem simple_graph_cycle_power_six_one_sanity : (simple_graph_cycle_power 6 1).Adj 0 5 ∧ ¬ (simple_graph_cycle_power 6 1).Adj 0 2 := by show ((0 : ZMod 6) ≠ 5 ∧ _) ∧ ¬ ((0 : ZMod 6) ≠ 2 ∧ _) decide