simple_graph_hop_word_length_one
Every hop of a simple graph G is the product of a one-element list of hops of G.
Statement
theorem simple_graph_hop_word_length_one {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : ∃ w : List (Equiv.Perm V), (∀ x ∈ w, simple_graph_is_hop G x) ∧ w.length = 1 ∧ w.prod = h
- Source
- folklore
- Verified
- 27 Oct 2026
- Axioms
Quot.soundpropext- 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.
Read back from the Lean
For any type V, any simple graph G on V, and any permutation h of V, if h is a hop on G (i.e., simple_graph_is_hop G h), then there exists a list w of permutations of V such that every element of w is a hop on G, the length of w is 1, and the product of the permutations in w equals h.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof provides the singleton list $[h]$ containing only $h$ as an explicit witness. Because $h$ is assumed to be a hop, every element in the list is a hop, and by definition the list has length $1$ and evaluates to product $h$.
The singleton list $[h]$ is a length-$1$ list of hops of $G$ whose product is $h$.
We supply the singleton list $[h]$ as the explicit witness for the existential quantifier. The condition that every element of $[h]$ is a hop simplifies to the assumption $hh$ that $h$ is a hop. The remaining two conditions—that the length of $[h]$ is $1$ and that the product of the elements in $[h]$ is $h$—hold definitionally by reflexivity.
exact ⟨[h], by simp [hh], rfl, rfl⟩
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.
/-- Every hop of a simple graph is a product of a length-1 list of hops. -/theorem simple_graph_hop_word_length_one {V : Type*} (G : SimpleGraph V) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : ∃ w : List (Equiv.Perm V), (∀ x ∈ w, simple_graph_is_hop G x) ∧ w.length = 1 ∧ w.prod = h := by exact ⟨[h], by simp [hh], rfl, rfl⟩