cone_necklace_cycle_adj
When m is at least three, successive cycle vertices are adjacent.
Statement
theorem cone_necklace_cycle_adj(m : ℕ) (hm : 3 ≤ m) (i : Fin m) : (cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (by omega)⟩
- Source
- Sanity lemma for the graph definition cone_necklace_graph, used in IN-584.
- Verified
- 06 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- cone_necklace_graphFor each natural m, the simple graph on vertices 0 through 2m has apex 2m adjacent to every other vertex. For each i from 0 to m−1, it…
The proof, explained
To show that vertex i and its cyclic successor (i + 1) % m are adjacent in the cone necklace graph, we unfold the graph definition: adjacency requires that the pair belongs to the edge set and that the two vertices are distinct. The pair matches the cycle edge at index i by definition. Assuming the vertices are equal gives i = (i + 1) % m, which is impossible both when i + 1 < m (giving i = i + 1) and when i + 1 = m (giving m = 1, contradicting 3 ≤ m).
The vertex indices i and (i + 1) % m are strictly less than 2 * m + 1, so they define valid vertices in Fin (2 * m + 1).
The theorem statement requires proofs that the vertex indices are bounded by 2 * m + 1. For the first vertex, since i < m and 3 ≤ m, linear arithmetic (`omega`) shows i < 2 * m + 1. For the second vertex, since 0 < m, `Nat.mod_lt` shows (i + 1) % m < m; combining this with m ≤ 2 * m + 1 via `lt_of_lt_of_le` proves (i + 1) % m < 2 * m + 1.
uses
lt_of_lt_of_le,Nat.mod_lt(cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (by omega)⟩ := by
The unordered pair {i, (i + 1) % m} is an edge of the cone necklace graph, so adjacency reduces to showing that the two vertices are distinct.
We unfold the definition of the cone necklace graph and the characterization of adjacency for edge-set graphs (`SimpleGraph.fromEdgeSet_adj`, `Set.mem_ofPred_eq`), which requires the pair of vertices to be in the edge set and the endpoints to be distinct. The edge set contains the cycle edges s(cycle j, cycle (next j)) for each j : Fin m. Selecting the cycle edge for index i (`Or.inr`, `Or.inl`) matches the required pair by reflexivity, leaving only the goal that the two vertices are distinct.
uses
SimpleGraph.fromEdgeSet_adj,Set.mem_ofPred_eq,Or.inr,Or.inlsimp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] refine ⟨Or.inr ⟨i, Or.inl rfl⟩, ?_⟩
Assuming the two vertices are equal implies i = (i + 1) % m as natural numbers, with i < m.
We assume for contradiction that the two vertices are equal (`intro h`). Applying `Fin.val` to both sides via `congrArg` gives the equality of their underlying natural numbers, i = (i + 1) % m. We also record that i < m from the definition of Fin m.
uses
congrArg,Fin.valintro h have hv := congrArg Fin.val h change i.val = (i.val + 1) % m at hv have hi := i.isLt
If i + 1 < m, the equality i = (i + 1) % m yields an immediate contradiction.
We split into cases on whether i + 1 < m. When i + 1 < m, the remainder (i + 1) % m simplifies to i + 1 by `Nat.mod_eq_of_lt`. The equality then becomes i = i + 1, which linear arithmetic (`omega`) recognizes as impossible.
uses
Nat.mod_eq_of_ltby_cases hlt : i.val + 1 < m · rw [Nat.mod_eq_of_lt hlt] at hv omega
If i + 1 ≥ m, the equality i = (i + 1) % m also yields a contradiction.
Since i < m and ¬(i + 1 < m), linear arithmetic shows i + 1 = m. Rewriting i + 1 as m gives i = m % m = 0 using `Nat.mod_self`. But then i + 1 = m implies 0 + 1 = m, so m = 1, which contradicts the hypothesis 3 ≤ m. Linear arithmetic (`omega`) detects this contradiction and closes the proof.
uses
Nat.mod_self· have heq : i.val + 1 = m := by omega rw [heq, Nat.mod_self] at hv omega
lt_of_lt_of_le- In a preorder, if a < b and b ≤ c, then a < c.
Nat.mod_lt- For any natural number x and positive natural number y, the remainder x % y is strictly less than y.
SimpleGraph.fromEdgeSet_adj- Two vertices in a graph defined from an edge set are adjacent if and only if the unordered pair between them belongs to the edge set and the two vertices are distinct.
Set.mem_ofPred_eq- An element belongs to a set defined by a predicate if and only if it satisfies the predicate.
Or.inr- Right introduction for disjunction: if B holds, then A ∨ B holds.
Or.inl- Left introduction for disjunction: if A holds, then A ∨ B holds.
congrArg- Applying a function to both sides of an equality preserves the equality.
Fin.val- Extracts the underlying natural number from a Fin n value.
Nat.mod_eq_of_lt- If a < b for natural numbers, then a % b = a.
Nat.mod_self- For any natural number n, n % n = 0.
- The theorem signature contains inline tactic proofs on lines 2 and 3 (using `omega` and `lt_of_lt_of_le` with `Nat.mod_lt`) to verify that the vertex indices are strictly less than 2 * m + 1.
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 cone_necklace_cycle_adj(m : ℕ) (hm : 3 ≤ m) (i : Fin m) : (cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (by omega)⟩ := by simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] refine ⟨Or.inr ⟨i, Or.inl rfl⟩, ?_⟩ intro h have hv := congrArg Fin.val h change i.val = (i.val + 1) % m at hv have hi := i.isLt by_cases hlt : i.val + 1 < m · rw [Nat.mod_eq_of_lt hlt] at hv omega · have heq : i.val + 1 = m := by omega rw [heq, Nat.mod_self] at hv omega