AFTD Auto-Formalizing Theoretical Domains

cone_necklace_next_radial_adj

theoremverified

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.

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

    lines 3–4

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

    lines 5–6

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

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

    lines 7–12

    uses congrArg, Fin.val, Nat.mod_lt

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

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