AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_hop_mem_leap_group

theoremverified

Every hop lies in the leap group.

Statement

theorem simple_graph_is_hop_mem_leap_group {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V)
    (hh : simple_graph_is_hop G h) : h ∈ simple_graph_leap_group G
Source
Sanity lemma for the leap group, arXiv:2610.18463 (The group generated by a graph's derangements), Definition 2.1.
Verified
15 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.
Used by 3

The proof, explained

The leap group of a simple graph $G$ is defined as the subgroup of permutations generated by the set of all hops on $G$. Since any generating set is a subset of the subgroup it generates, applying `Subgroup.subset_closure` directly establishes that any hop $h$ belongs to the leap group.

  1. The permutation $h$ belongs to the leap group of $G$.

    By definition, the leap group of $G$ is the subgroup generated by the set of all hops of $G$, namely $\\mathrm{Subgroup.closure}\\{h \\mid \\mathrm{simple\\_graph\\_is\\_hop}\\,G\\,h\\}$. Applying `Subgroup.subset_closure` to the hypothesis $hh$ that $h$ is a hop shows immediately that $h$ lies in this generated subgroup.

    line 3

    uses Subgroup.subset_closure

      Subgroup.subset_closure hh
Subgroup.subset_closure
Any subset of a group is contained in the subgroup it generates (its closure).

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem simple_graph_is_hop_mem_leap_group {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V)    (hh : simple_graph_is_hop G h) : h ∈ simple_graph_leap_group G :=  Subgroup.subset_closure hh
See it in the graphDiscuss this resultChallenge it