AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_reclusive

def

A simple graph G is reclusive if it admits a hop and the identity permutation on its vertex set can be written as a product of an odd number of hops of G.

Statement

def simple_graph_is_reclusive {V : Type*} (G : SimpleGraph V) : Prop
Defined in
scout/2610-18463-the-group-generated-by-a-graph-s-derangements.md:345
Verified
15 Oct 2026
Axioms
none listed
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

A simple graph G on vertex type V is defined to be reclusive if both: 1. There exists a permutation h of V such that for all vertices v : V, v is adjacent to h(v) in G (i.e., h is a "hop"); and 2. There exists a list l of permutations of V such that: - every permutation h in l is a hop for G (for all v : V, v is adjacent to h(v)), - the length of l is odd, and - the product of the permutations in l (in the group Equiv.Perm V) equals 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.

Lean source view module on GitHub

/-- A graph is reclusive if it admits a hop and the identity permutation is an odd-length product of hops. -/
def simple_graph_is_reclusive {V : Type*} (G : SimpleGraph V) : Prop :=
  (∃ h : Equiv.Perm V, simple_graph_is_hop G h) ∧
  ∃ l : List (Equiv.Perm V), (∀ h ∈ l, simple_graph_is_hop G h) ∧ Odd l.length ∧ l.prod = 1
See it in the graphDiscuss this resultChallenge it