AFTD Auto-Formalizing Theoretical Domains

cone_necklace_radial_adj

theoremverified

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.

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

    line 2

        (cone_necklace_graph m).Adj ⟨i.val, by omega⟩ ⟨m + i.val, by omega⟩ := by
  2. 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.

    lines 3–4

    uses SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq, Or.inr, Or.inl

      simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq]
      refine ⟨Or.inr ⟨i, Or.inr (Or.inl rfl)⟩, ?_⟩
  3. 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.

    lines 5–9

    uses congrArg, Fin.val

      intro 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

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