AFTD Auto-Formalizing Theoretical Domains

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 s at some handshake of the sequence seq (the union of the touch sets of the…
  • seq_touchers_subset_contamContamination is monotone in the following sense: after running the sequence seq from the contamination map t, the contamination of…
  • handshake_touchersThe set of vertices that directly touch the glove side s during the handshake h: for a single handshake x|a opp(a)|y the vertex x…
  • 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 h is clean with respect to the contamination map t and the vertex v touches the side s during h, 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 seq starting from the contamination map t. (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.

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 Γ
See it in the graphDiscuss this resultChallenge it