AFTD Auto-Formalizing Theoretical Domains

cone_necklace_cycle_adj

theoremverified

When m is at least three, successive cycle vertices are adjacent.

Statement

theorem cone_necklace_cycle_adj(m : ℕ) (hm : 3 ≤ m) (i : Fin m) :
    (cone_necklace_graph m).Adj ⟨i.val, by omega⟩
      ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (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 vertex i and its cyclic successor (i + 1) % m are adjacent in the cone necklace graph, we unfold the graph definition: adjacency requires that the pair belongs to the edge set and that the two vertices are distinct. The pair matches the cycle edge at index i by definition. Assuming the vertices are equal gives i = (i + 1) % m, which is impossible both when i + 1 < m (giving i = i + 1) and when i + 1 = m (giving m = 1, contradicting 3 ≤ m).

  1. The vertex indices i and (i + 1) % m are strictly less than 2 * m + 1, so they define valid vertices in Fin (2 * m + 1).

    The theorem statement requires proofs that the vertex indices are bounded by 2 * m + 1. For the first vertex, since i < m and 3 ≤ m, linear arithmetic (`omega`) shows i < 2 * m + 1. For the second vertex, since 0 < m, `Nat.mod_lt` shows (i + 1) % m < m; combining this with m ≤ 2 * m + 1 via `lt_of_lt_of_le` proves (i + 1) % m < 2 * m + 1.

    lines 2–3

    uses lt_of_lt_of_le, Nat.mod_lt

        (cone_necklace_graph m).Adj ⟨i.val, by omega⟩
          ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (by omega)⟩ := by
  2. The unordered pair {i, (i + 1) % m} is an edge of the cone necklace graph, so adjacency reduces to showing that the two vertices are distinct.

    We unfold the definition of the cone necklace graph and the characterization of adjacency for edge-set graphs (`SimpleGraph.fromEdgeSet_adj`, `Set.mem_ofPred_eq`), which requires the pair of vertices to be in the edge set and the endpoints to be distinct. The edge set contains the cycle edges s(cycle j, cycle (next j)) for each j : Fin m. Selecting the cycle edge for index i (`Or.inr`, `Or.inl`) matches the required pair by reflexivity, leaving only the goal that the two vertices are distinct.

    lines 4–5

    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.inl rfl⟩, ?_⟩
  3. Assuming the two vertices are equal implies i = (i + 1) % m as natural numbers, with i < m.

    We assume for contradiction that the two vertices are equal (`intro h`). Applying `Fin.val` to both sides via `congrArg` gives the equality of their underlying natural numbers, i = (i + 1) % m. We also record that i < m from the definition of Fin m.

    lines 6–9

    uses congrArg, Fin.val

      intro h
      have hv := congrArg Fin.val h
      change i.val = (i.val + 1) % m at hv
      have hi := i.isLt
  4. If i + 1 < m, the equality i = (i + 1) % m yields an immediate contradiction.

    We split into cases on whether i + 1 < m. When i + 1 < m, the remainder (i + 1) % m simplifies to i + 1 by `Nat.mod_eq_of_lt`. The equality then becomes i = i + 1, which linear arithmetic (`omega`) recognizes as impossible.

    lines 10–12

    uses Nat.mod_eq_of_lt

      by_cases hlt : i.val + 1 < m
      · rw [Nat.mod_eq_of_lt hlt] at hv
        omega
  5. If i + 1 ≥ m, the equality i = (i + 1) % m also yields a contradiction.

    Since i < m and ¬(i + 1 < m), linear arithmetic shows i + 1 = m. Rewriting i + 1 as m gives i = m % m = 0 using `Nat.mod_self`. But then i + 1 = m implies 0 + 1 = m, so m = 1, which contradicts the hypothesis 3 ≤ m. Linear arithmetic (`omega`) detects this contradiction and closes the proof.

    lines 13–15

    uses Nat.mod_self

      · have heq : i.val + 1 = m := by omega
        rw [heq, Nat.mod_self] at hv
        omega
lt_of_lt_of_le
In a preorder, if a < b and b ≤ c, then a < c.
Nat.mod_lt
For any natural number x and positive natural number y, the remainder x % y is strictly less than y.
SimpleGraph.fromEdgeSet_adj
Two vertices in a graph defined from an edge set are adjacent if and only if the unordered pair between them belongs to 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 it satisfies the predicate.
Or.inr
Right introduction for disjunction: if B holds, then A ∨ B holds.
Or.inl
Left introduction for disjunction: if A holds, then A ∨ B holds.
congrArg
Applying a function to both sides of an equality preserves the equality.
Fin.val
Extracts the underlying natural number from a Fin n value.
Nat.mod_eq_of_lt
If a < b for natural numbers, then a % b = a.
Nat.mod_self
For any natural number n, n % n = 0.

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_cycle_adj(m : ℕ) (hm : 3 ≤ m) (i : Fin m) :    (cone_necklace_graph m).Adj ⟨i.val, by omega⟩      ⟨(i.val + 1) % m, by exact lt_of_lt_of_le (Nat.mod_lt _ (by omega)) (by omega)⟩ := by  simp only [cone_necklace_graph, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq]  refine ⟨Or.inr ⟨i, Or.inl rfl⟩, ?_⟩  intro h  have hv := congrArg Fin.val h  change i.val = (i.val + 1) % m at hv  have hi := i.isLt  by_cases hlt : i.val + 1 < m  · rw [Nat.mod_eq_of_lt hlt] at hv    omega  · have heq : i.val + 1 = m := by omega    rw [heq, Nat.mod_self] at hv    omega
See it in the graphDiscuss this resultChallenge it