AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_hop_closed

def

An edge subset F of a finite simple graph G is hop-closed (hop-maximal) if F is a subset of the edge set of G and for every edge e in E(G) \ F, the spanning subgraph with edges F ∪ {e} has strictly more hops than the spanning subgraph with edges F.

Statement

def simple_graph_is_hop_closed {V : Type*} [Fintype V] (G : SimpleGraph V) (F : Set (Sym2 V)) : Prop
Defined in
arXiv:2610.18463 Question 5.9: The group generated by a graph's derangements
Verified
25 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.
Used by 2

Read back from the Lean

For a finite type V, a simple graph G on V, and a set of unordered pairs F : Set (Sym2 V), simple_graph_is_hop_closed G F asserts that: 1. F is a subset of the edge set of G (F ⊆ G.edgeSet), and 2. For every edge e in G.edgeSet \ F, the number of permutations h : Equiv.Perm V that are "hops" in SimpleGraph.fromEdgeSet F (meaning every vertex v is adjacent to h(v) in the graph whose edges are F) is strictly less than the number of permutations h : Equiv.Perm V that are "hops" in SimpleGraph.fromEdgeSet (insert e F).

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

/-- An edge subset of a finite simple graph is hop-closed (hop-maximal) if adding any edge strictly increases its number of hops. -/
def simple_graph_is_hop_closed {V : Type*} [Fintype V] (G : SimpleGraph V) (F : Set (Sym2 V)) : Prop :=
  F ⊆ G.edgeSet ∧
  ∀ e ∈ G.edgeSet \ F,
    Nat.card {h : Equiv.Perm V // simple_graph_is_hop (SimpleGraph.fromEdgeSet F) h} <
    Nat.card {h : Equiv.Perm V // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert e F)) h}
See it in the graphDiscuss this resultChallenge it