AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_hop_inv

theoremverified

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

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).

  1. 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).

    line 3

      intro v
  2. The 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.

    line 4

      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

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
See it in the graphDiscuss this resultChallenge it