CleanHandshakeSeq
Inductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
Statement
inductive CleanHandshakeSeq {V : Type*} {Γ : Type*} [DecidableEq Γ] : List (Handshake V Γ) → (Γ × Bool → Set V) → 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_is_cleanA handshake is clean with respect to a contamination map $t : \Gamma \times \mathrm{Bool} \to \mathrm{Set}(V)$ if no player directly…
- handshake_update_contamThe updated contamination map after a handshake: players add their germs to the glove sides they touch directly, and in a double handshake…
- Used by 9
- glove_number_k2The glove number of the complete graph $K_2$ is equal to 1.
- 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.
- has_clean_handshake_seqA simple graph $G$ has a clean handshake sequence with $k$ gloves if there exists a sequence of handshakes over glove type…
- 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_posFor every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.
- seq_touchers_subsingletonIn a clean handshake sequence, each glove side is directly touched by at most one vertex: the set of touching vertices of a side is a…
- 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.
Read back from the Lean
An inductive predicate CleanHandshakeSeq parameterized by types V and Γ (with [DecidableEq Γ]), taking a sequence of handshakes seq : List (Handshake V Γ) and a contamination map t : Γ × Bool → Set V. It asserts that the sequence of handshakes can be executed cleanly without cross-contamination starting from state t:
1. nil: For any initial contamination state t, the empty sequence [] is clean.
2. cons: A non-empty sequence h :: seq is clean from state t if:
- handshake_is_clean h t holds for the first handshake h, and
- CleanHandshakeSeq seq (handshake_update_contam h t) holds for the remaining handshakes under the contamination state updated by h.
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
/-- Predicate asserting a sequence of handshakes is clean starting from a contamination state. -/ inductive CleanHandshakeSeq {V : Type*} {Γ : Type*} [DecidableEq Γ] : List (Handshake V Γ) → (Γ × Bool → Set V) → Prop where | nil (t : Γ × Bool → Set V) : CleanHandshakeSeq [] t | cons (h : Handshake V Γ) (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V) : handshake_is_clean h t → CleanHandshakeSeq seq (handshake_update_contam h t) → CleanHandshakeSeq (h :: seq) t