has_clean_handshake_seq
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
- glove_number_k2The glove number of the complete graph $K_2$ is equal to 1.
- has_clean_handshake_seq_monoIf a graph $G$ admits a clean handshake sequence with $k$ gloves and $k \le k'$, then it admits one with $k'$ gloves.
- glove_number_k3The glove number of the complete graph $K_3$ is equal to 2.
- glove_number_complete_graph_no_zero_glovesFor any integer $n \ge 2$, there is no clean handshake sequence with zero gloves covering all edges of the complete graph $K_n$.
- glove_number_complete_graph_le_iffFor $n \ge 2$ and every $k$, the glove number of $K_n$ is at most $k$ if and only if $K_n$ has a clean handshake sequence with $k$ gloves.
- glove_number_le_iff_has_clean_handshake_seqIf some number of gloves suffices for a graph $G$, then for every $k$ the glove number of $G$ is at most $k$ if and only if $G$ has a…
- glove_number_complete_graph_upper_boundFor all integers $n \ge 2$, the glove number of the complete graph $K_n$ is at most $n - 1$.
- glove_number_complete_graph_eq_of_not_has_seqFor any integer $n \\ge 2$, if no clean handshake sequence using $n - 2$ gloves covers all edges of $K_n$, then the glove number of $K_n$…
- glove_number_complete_graph_posFor every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.
- glove_numberThe glove number $\mathrm{gl}(G)$ of a simple graph $G$ is the minimum number of gloves $k \in \mathbb{N}$ admitting a clean handshake…
- has_clean_handshake_seq_succIf a graph $G$ admits a clean handshake sequence with $k$ gloves, then it admits one with $k+1$ gloves: an extra glove can be left unused.
- glove_number_complete_graph_eq_iff_not_has_seqFor any integer $n \\ge 2$, the glove number of the complete graph $K_n$ is equal to $n - 1$ if and only if no clean handshake sequence…
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