cone_necklace_radial_adj
Each cycle vertex is adjacent to its corresponding private vertex.
Statement
theorem cone_necklace_radial_adj(m : ℕ) (i : Fin m) : (cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨m + i.val, 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 cycle vertex i and private vertex m + i are adjacent in the cone necklace graph, we first verify that the edge connecting them belongs to the graph's edge set by definition of the radial edges. We then show that the two vertices are distinct: if they were equal, their underlying natural numbers would satisfy i = m + i, which contradicts i < m.
The indices i and m + i are valid elements of Fin (2m + 1). automation
The bounds i < 2m + 1 and m + i < 2m + 1 are proved by linear arithmetic.
(cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨m + i.val, by omega⟩ := by
The edge between cycle vertex i and private vertex m + i is in the edge set of the graph, reducing adjacency to showing the vertices are distinct.
Unfolding the definition of the graph and the characterization of adjacency in a graph built from an edge set, adjacency holds if the pair is in the edge set and the endpoints are distinct. The edge set contains the radial edges connecting cycle vertex i to private vertex m + i, which holds by reflexivity.
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.inr (Or.inl rfl)⟩, ?_⟩
The vertices i and m + i are distinct.
Assuming for contradiction that the vertices are equal, taking their underlying natural values yields i = m + i. Since i < m, linear arithmetic derives a contradiction.
uses
congrArg,Fin.valintro h have hv := congrArg Fin.val h have hi := i.isLt simp only at hv omega
SimpleGraph.fromEdgeSet_adj- Adjacency in a graph constructed from an edge set s means the unordered pair {v, w} is in s and v ≠ w
Set.mem_ofPred_eq- Membership of x in {y | p y} is definitionally p x
Or.inr- A proof of b implies a ∨ b
Or.inl- A proof of a implies a ∨ b
congrArg- If two inputs are equal, applying a function to both yields equal results
Fin.val- The underlying natural number of an element of Fin n
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_radial_adj(m : ℕ) (i : Fin m) : (cone_necklace_graph m).Adj ⟨i.val, 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.inl rfl)⟩, ?_⟩ intro h have hv := congrArg Fin.val h have hi := i.isLt simp only at hv omega