AFTD Auto-Formalizing Theoretical Domains

simple_graph_hop_word_length_zero

theoremverified

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.

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

    line 4

      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

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