AFTD Auto-Formalizing Theoretical Domains

op_543_completeGraph_two_hop_word_length_le_one

theoremverified

For the complete graph K₂ on 2 vertices, every element of its leap group is the product of at most 1 hop.

Statement

theorem op_543_completeGraph_two_hop_word_length_le_one :
    ∀ g ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 2)),
      ∃ w : List (Equiv.Perm (Fin 2)), (∀ h ∈ w, simple_graph_is_hop ⊤ h) ∧
        w.length ≤ 1 ∧ w.prod = g
Source
step towards op_543_leap_group_universal_quadratic_word_diameter
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
  • simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.

Lean source view module on GitHub

/-- For the complete graph K₂ on 2 vertices, every element of its leap group is the product of at most 1 hop. -/
theorem op_543_completeGraph_two_hop_word_length_le_one :
    ∀ g ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 2)),
      ∃ w : List (Equiv.Perm (Fin 2)), (∀ h ∈ w, simple_graph_is_hop ⊤ h) ∧
        w.length ≤ 1 ∧ w.prod = g := by
  intro g _
  have h_or : g = 1 ∨ g = Equiv.swap 0 1 := by
    fin_cases g <;> decide
  cases h_or with
  | inl h1 =>
    refine ⟨[], by simp, by norm_num, by simp [h1]⟩
  | inr h2 =>
    refine ⟨[g], ?_, le_rfl, by simp⟩
    intro h hh
    simp only [List.mem_singleton] at hh
    subst hh
    rw [h2]
    intro v
    fin_cases v <;> decide
See it in the graphDiscuss this resultChallenge it