simple_graph_is_hop_inv
The inverse of a hop is a hop (the graph is undirected).
Statement
theorem simple_graph_is_hop_inv {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : simple_graph_is_hop G h⁻¹
- Source
- Sanity lemma for hops, arXiv:2610.18463 (The group generated by a graph's derangements), Sec. 2.1 (the inverse of a hop is a hop, so Λ₃ = Λ₁).
- Verified
- 15 Oct 2026
- Axioms
Quot.sound- Built on 1
- 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.
- Used by 5
- simple_graph_normalized_hop_two_wordEvery normalized allowed permutation is the product of exactly two actual hops on an undirected graph. No vertex is allowed to wait during…
- simple_graph_normalized_hop_conjugate_memConjugating one normalized allowed permutation by the baseline yields an element of the normalized SUBGROUP, without claiming it stays in…
- simple_graph_normalized_hop_group_square_invThe inverse square of a baseline hop belongs to the normalized subgroup.
- simple_graph_normalized_hop_inverse_two_wordThe inverse of a normalized allowed permutation also has a two-hop realization, although it need not itself be normalized allowed.
- simple_graph_normalized_hop_group_leFor a fixed baseline hop, its normalized subgroup is contained in the original leap group.
The proof, explained
To show that the inverse permutation h⁻¹ of a hop h is also a hop, we must verify that each vertex v is adjacent to h⁻¹(v). Evaluating the hop property of h at the vertex h⁻¹(v) yields that h⁻¹(v) is adjacent to h(h⁻¹(v)) = v. By symmetry of adjacency in a simple graph, v is adjacent to h⁻¹(v).
To show that h⁻¹ is a hop, it suffices to show that an arbitrary vertex v is adjacent to h⁻¹(v).
By definition, a permutation is a hop on G if every vertex is adjacent to its image. Unfolding this definition for h⁻¹ and introducing an arbitrary vertex v reduces the goal to proving that v is adjacent to h⁻¹(v).
intro vThe vertex v is adjacent to h⁻¹(v) in G.
Instantiating the hypothesis that h is a hop at the vertex h⁻¹(v) shows that h⁻¹(v) is adjacent to h(h⁻¹(v)). Because adjacency in a simple graph is symmetric, h(h⁻¹(v)) is adjacent to h⁻¹(v). Simplifying h(h⁻¹(v)) to v finishes the proof.
simpa using (hh (h⁻¹ v)).symm
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem simple_graph_is_hop_inv {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : simple_graph_is_hop G h⁻¹ := by intro v simpa using (hh (h⁻¹ v)).symm