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