glove_number
The glove number $\mathrm{gl}(G)$ of a simple graph $G$ is the minimum number of gloves $k \in \mathbb{N}$ admitting a clean handshake sequence covering all edges of $G$, defined as the infimum of the set of such $k$.
Statement
noncomputable def glove_number {V : Type*} (G : SimpleGraph V) : ℕ
- Defined in
- scout/2610-17602-clean-handshake-sequences.md:222
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 10
- glove_number_complete_graph_eq_iff_geFor any integer $n \ge 2$, the glove number of the complete graph $K_n$ is equal to $n - 1$ if and only if it is at least $n - 1$.
- 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_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_number_complete_graph_le_threeFor any integer $n$ such that $2 \\le n \\le 3$, the glove number of the complete graph $K_n$ is equal to $n - 1$.
- 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 and a simple graph G on V, glove_number G is defined as the infimum (in ℕ, with sInf ∅ = 0) of the set of natural numbers k such that there exists a clean handshake sequence using k gloves covering all edges of G.
Specifically, has_clean_handshake_seq G k asserts the existence of a finite list seq : List (Handshake V (Fin k)) such that:
1. seq is a valid clean handshake sequence starting from the empty contamination state fun _ => ∅.
2. For every edge e in G.edgeSet, 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
/-- The glove number of a simple graph. -/ noncomputable def glove_number {V : Type*} (G : SimpleGraph V) : ℕ := sInf {k : ℕ | has_clean_handshake_seq G k}