simple_graph_is_hop_mem_leap_group
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
- simple_graph_completeGraph_three_leap_closed_not_intersection_closedThe collection of leap-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
- op_300_hypercube_two_leap_group_cardThe 2-dimensional hypercube graph Q₂ (the 4-cycle C₄) has leap group of cardinality 8.
- op_300_hypercube_one_leap_group_cardThe hypercube graph Q₁ (the path K₂) has leap group of cardinality 2.
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.
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.
uses
Subgroup.subset_closureSubgroup.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