cone_necklace_apex_adj
The apex is adjacent to every other vertex.
Statement
theorem cone_necklace_apex_adj(m : ℕ) (v : Fin (2 * m + 1)) (h : v.val ≠ 2 * m) : (cone_necklace_graph m).Adj ⟨2 * m, by omega⟩ v
- 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
The cone necklace graph contains an edge between the apex vertex (index 2m) and every other vertex. Because the vertex v has index different from 2m, it is distinct from the apex. Therefore, the unordered pair connecting the apex and v satisfies the first edge constructor of the graph and connects distinct vertices, proving they are adjacent.
The vertex v is not equal to the apex vertex.
The apex is the vertex with index 2m, which is valid since 2m < 2m + 1 by linear arithmetic. Assuming for contradiction that v equals the apex, applying Fin.val implies that the underlying value of v is 2m, which directly contradicts the assumption h that v.val ≠ 2m.
uses
congrArg,Fin.val(cone_necklace_graph m).Adj ⟨2 * m, by omega⟩ v := by have hv : v ≠ (⟨2 * m, by omega⟩ : Fin (2 * m + 1)) := by intro e apply h exact congrArg Fin.val e
Adjacency of the apex and v reduces to showing that the unordered pair between them is in the edge set and that they are distinct.
Unfolding the definition of the cone necklace graph and simplifying with the characterisation of adjacency in a graph built from an edge set (SimpleGraph.fromEdgeSet_adj) and set comprehension membership (Set.mem_ofPred_eq).
uses
SimpleGraph.fromEdgeSet_adj,Set.mem_ofPred_eqsimp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq]The apex and v form an edge between distinct vertices, establishing adjacency.
The pair s(apex, v) belongs to the edge set by choosing v as the witness in the apex-incident edge constructor, since v ≠ apex was established earlier. Furthermore, the apex and v are distinct by symmetry of inequality (Ne.symm applied to hv).
uses
Or.inl,Ne.symmexact ⟨Or.inl ⟨v, hv, rfl⟩, Ne.symm hv⟩
congrArg- If two arguments are equal, applying the same function to both yields equal values.
Fin.val- The projection mapping an element of Fin n to its underlying natural number.
SimpleGraph.fromEdgeSet_adj- In a graph constructed from an edge set, two vertices are adjacent if and only if the unordered pair between them is in 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 the predicate holds for that element.
Or.inl- If a proposition holds, then any disjunction with that proposition as its left disjunct also holds.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
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_apex_adj(m : ℕ) (v : Fin (2 * m + 1)) (h : v.val ≠ 2 * m) : (cone_necklace_graph m).Adj ⟨2 * m, by omega⟩ v := by have hv : v ≠ (⟨2 * m, by omega⟩ : Fin (2 * m + 1)) := by intro e apply h exact congrArg Fin.val e simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq] exact ⟨Or.inl ⟨v, hv, rfl⟩, Ne.symm hv⟩