AFTD Auto-Formalizing Theoretical Domains

cone_necklace_apex_adj

theoremverified

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.

  1. 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.

    lines 2–6

    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
  2. 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).

    line 7

    uses SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq

      simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq]
  3. 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).

    line 8

    uses Or.inl, Ne.symm

      exact ⟨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

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⟩
See it in the graphDiscuss this resultChallenge it