AFTD Auto-Formalizing Theoretical Domains

has_clean_handshake_seq

def

A simple graph $G$ has a clean handshake sequence with $k$ gloves if there exists a sequence of handshakes over glove type $\mathrm{Fin}(k)$ that is clean starting from the empty contamination map and covers every edge of $G$.

Statement

def has_clean_handshake_seq {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
scout/2610-17602-clean-handshake-sequences.md:222
Verified
18 Oct 2026
Axioms
none listed
Built on 3
  • HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
  • handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
  • CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
Used by 12

Read back from the Lean

Given a type V, a simple graph G on V, and a natural number k, has_clean_handshake_seq G k asserts that there exists a finite list seq of handshakes using k gloves (indexed by Fin k) such that: 1. seq is a clean handshake sequence starting with completely uncontaminated gloves (every glove side has an empty contamination set). 2. Every edge e in G.edgeSet is covered by at least one handshake in seq (i.e., for every edge e of G, there exists some handshake h in seq whose associated edge handshake_edge h equals e).

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

/-- Whether a graph admits a clean handshake sequence using k gloves. -/
def has_clean_handshake_seq {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ∃ seq : List (Handshake V (Fin k)),
    CleanHandshakeSeq seq (fun _ => ∅) ∧
    ∀ e ∈ G.edgeSet, ∃ h ∈ seq, handshake_edge h = e
See it in the graphDiscuss this resultChallenge it