AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_one

theoremverified

The identity is allowed relative to any baseline hop.

Statement

theorem simple_graph_normalized_hop_one {V : Type*} (G : SimpleGraph V)
    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) :
    simple_graph_normalized_hop G h₀ 1
Source
Uniform structural helper for IN-262 / OP-543, using the hop and leap-group definitions of arXiv:2610.18463. The universal quadratic word bound is a question proposed here, not a theorem of that paper. No diameter estimate or research advance is claimed by this algebraic normalization.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_normalized_hopA permutation p is allowed relative to baseline h0 when h0*p is an actual hop. Relative p may fix vertices; the resulting actual hop still…
  • 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.

The proof, explained

By definition, a permutation is a normalized hop relative to a baseline permutation $h₀$ if its composition with $h₀$ is a hop in the graph. For the identity permutation $1$, the composition $h₀ * 1$ is just $h₀$. The assertion therefore reduces immediately to the hypothesis that $h₀$ is already a hop.

  1. The identity permutation $1$ is a normalized hop in $G$ relative to $h₀$. automation

    By definition of `simple_graph_normalized_hop`, a permutation $p$ is a normalized hop relative to $h₀$ if $h₀ * p$ is a hop in $G$. For $p = 1$, the product $h₀ * 1$ simplifies to $h₀$. The goal thus reduces to showing that $h₀$ is a hop in $G$, which is precisely the hypothesis `hh₀`.

    line 4

    uses simple_graph_normalized_hop

      simpa [simple_graph_normalized_hop] using hh₀
simple_graph_normalized_hop
A permutation $p$ is a normalized hop relative to a baseline permutation $h₀$ on a graph $G$ if the composed permutation $h₀ * p$ is a hop in $G$ (that is, every vertex $v$ is adjacent to $(h₀ * p)(v)$).

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_normalized_hop_one {V : Type*} (G : SimpleGraph V)    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) :    simple_graph_normalized_hop G h₀ 1 := by  simpa [simple_graph_normalized_hop] using hh₀
See it in the graphDiscuss this resultChallenge it