AFTD Auto-Formalizing Theoretical Domains

simple_graph_hop_word_length_one

theoremverified

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

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

    line 5

      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

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