Handshake
inductive
A handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the other is bare-handed) or double-gloved (each vertex wears a glove side inside, and the outer sides touch).
Statement
inductive Handshake (V : Type*) (Γ : Type*)
- Defined in
- scout/2610-17602-clean-handshake-sequences.md:154
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 20
- seq_touchersThe set of vertices that directly touch the glove side
sat some handshake of the sequenceseq(the union of the touch sets of the… - seq_touchers_subset_contamContamination is monotone in the following sense: after running the sequence
seqfrom the contamination mapt, the contamination of… - handshake_touchersThe set of vertices that directly touch the glove side
sduring the handshakeh: for a single handshakex|a opp(a)|ythe vertexx… - glove_number_k2The glove number of the complete graph $K_2$ is equal to 1.
- handshake_left_sideThe glove side directly touched by the first vertex of a handshake: in a single handshake $x|a\overline{a}|y$ the side $a$ worn by $x$, in…
- glove_number_k3The glove number of the complete graph $K_3$ is equal to 2.
- 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…
- CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
- 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.
- handshake_right_sideThe glove side directly touched by the second vertex of a handshake: in a single handshake $x|a\overline{a}|y$ the opposite side…
- 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$.
- handshake_clean_update_contam_subset_toucherIf the handshake
his clean with respect to the contamination maptand the vertexvtouches the sidesduringh, then after… - 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…
- handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
- glove_number_complete_graph_posFor every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.
- seq_contamThe contamination map obtained by running the handshake sequence
seqstarting from the contamination mapt. (This is the index-free… - 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.
- seq_touchersThe set of vertices that directly touch the glove side
Read back from the Lean
An inductive type Handshake parameterized by two types V and Γ, with two constructors:
- single, which takes an element x : V, a pair a : Γ × Bool, and an element y : V, returning Handshake V Γ;
- double, which takes an element x : V, two pairs a : Γ × Bool and b : Γ × Bool, and an element y : V, returning Handshake V Γ.
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 single-gloved or double-gloved handshake between two players. -/ inductive Handshake (V : Type*) (Γ : Type*) where | single (x : V) (a : Γ × Bool) (y : V) : Handshake V Γ | double (x : V) (a : Γ × Bool) (b : Γ × Bool) (y : V) : Handshake V Γ