cone_necklace_next_radial_adj
Each private vertex is adjacent to the next cycle vertex.
Statement
theorem cone_necklace_next_radial_adj(m : ℕ) (i : Fin m) : (cone_necklace_graph m).Adj ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by have := i.isLt; omega)) (by omega)⟩ ⟨m + i.val, by omega⟩
- Source
- Sanity lemma for 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 the next cycle vertex and the i-th private vertex are adjacent in the cone necklace graph, we unfold the graph's definition into membership in its edge set and distinctness of the two endpoints. The edge set explicitly contains the pair connecting private vertex i to the next cycle vertex (i + 1) mod m. Finally, the vertices are distinct because (i + 1) mod m is strictly less than m, while m + i is at least m.
The indices (i + 1) % m and m + i are valid vertices in Fin (2 * m + 1).
Since i < m, we have 0 < m, so (i + 1) % m < m ≤ 2 * m + 1 by Nat.mod_lt and lt_of_lt_of_le. Similarly, m + i < 2 * m + 1 by linear arithmetic.
uses
lt_of_lt_of_le,Nat.mod_lt⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by have := i.isLt; omega)) (by omega)⟩ ⟨m + i.val, by omega⟩ := by
The pair formed by the next cycle vertex and the i-th private vertex is an edge of the graph.
Unfolding the definition of cone_necklace_graph and adjacency via SimpleGraph.fromEdgeSet_adj and Set.mem_ofPred_eq, the goal reduces to showing that the unordered pair of vertices is in the edge set and that the vertices are distinct. The pair matches the third type of cycle-to-private edge (cycle (next i), privateVertex i) for index i.
uses
SimpleGraph.fromEdgeSet_adj,cone_necklace_graph,Set.mem_ofPred_eq,Or.inrsimp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] refine ⟨Or.inr ⟨i, Or.inr (Or.inr rfl)⟩, ?_⟩
The next cycle vertex and the i-th private vertex are distinct.
Assume for contradiction that the two vertices are equal. Applying Fin.val via congrArg implies (i + 1) % m = m + i. But since 0 < m, Nat.mod_lt gives (i + 1) % m < m, whereas m + i ≥ m, which is a contradiction by linear arithmetic.
uses
congrArg,Fin.val,Nat.mod_ltintro h have hv := congrArg Fin.val h change (i.val + 1) % m = m + i.val at hv have hi := i.isLt have hlt := Nat.mod_lt (i.val + 1) (by omega : 0 < m) omega
lt_of_lt_of_le- Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.mod_lt- For any positive divisor y, x mod y is strictly less than y.
SimpleGraph.fromEdgeSet_adj- Adjacency in a graph defined from an edge set s means the unordered pair {v, w} belongs to s and v ≠ w.
cone_necklace_graph- The graph on 2m + 1 vertices consisting of an apex connected to all other vertices, an m-cycle, and each cycle vertex i connected to a private vertex m + i, which in turn connects to the next cycle vertex (i + 1) mod m.
Set.mem_ofPred_eq- Set membership in a comprehension {x | p x} is definitionally equivalent to the predicate p x.
Or.inr- Introduces the right disjunct of a disjunction: b implies a ∨ b.
congrArg- Equality is preserved under applying a function: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.val- The projection from Fin n to its underlying natural number.
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_next_radial_adj(m : ℕ) (i : Fin m) : (cone_necklace_graph m).Adj ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by have := i.isLt; omega)) (by omega)⟩ ⟨m + i.val, by omega⟩ := by simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] refine ⟨Or.inr ⟨i, Or.inr (Or.inr rfl)⟩, ?_⟩ intro h have hv := congrArg Fin.val h change (i.val + 1) % m = m + i.val at hv have hi := i.isLt have hlt := Nat.mod_lt (i.val + 1) (by omega : 0 < m) omega