simple_graph_hop_word_length_zero
The identity permutation on the vertices of a simple graph G is the product of the empty list of hops of G.
Statement
theorem simple_graph_hop_word_length_zero {V : Type*} (G : SimpleGraph V) : ∃ w : List (Equiv.Perm V), (∀ x ∈ w, simple_graph_is_hop G x) ∧ w.length = 0 ∧ w.prod = 1
- Source
- arXiv:2610.18463, Section 2
- 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 and any simple graph G with vertices in V, there exists a list w of permutations of V (Equiv.Perm V) such that every permutation x in w satisfies simple_graph_is_hop G x, the length of w is 0, and the product of the permutations in w is the identity permutation 1.
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 theorem is proved by choosing the empty list of permutations as an explicit witness. The condition that every element is a hop holds vacuously, and both its length being 0 and its product being the identity permutation hold by definition.
The empty list [] witnesses the existential quantifier, satisfying all three required properties.
We supply the empty list of permutations `[]` as the witness. This produces three subgoals: first, the universal quantification `∀ x ∈ [], simple_graph_is_hop G x` holds vacuously because the empty list contains no elements (discharged by `simp`); second, `[].length = 0` holds by definition (`rfl`); third, the empty product `[].prod = 1` evaluates to the identity permutation by definition (`rfl`).
exact ⟨[], by simp, 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.
/-- The identity permutation on the vertices of a simple graph is an empty product of hops. -/theorem simple_graph_hop_word_length_zero {V : Type*} (G : SimpleGraph V) : ∃ w : List (Equiv.Perm V), (∀ x ∈ w, simple_graph_is_hop G x) ∧ w.length = 0 ∧ w.prod = 1 := by exact ⟨[], by simp, rfl, rfl⟩