glove_number_complete_graph_le_iff
For $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.
Statement
theorem glove_number_complete_graph_le_iff (n : ℕ) (hn : 2 ≤ n) (k : ℕ) :
glove_number (SimpleGraph.completeGraph (Fin n)) ≤ k ↔
has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k- Source
- step towards glove_number_complete_graph_open_problem
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_posFor every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.
- HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
- 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…
- 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$.
- 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…
- Used by 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…
The proof, explained
The proof applies the general characterization `glove_number_le_iff_has_clean_handshake_seq`, which reduces the equivalence to showing that K_n admits at least one clean handshake sequence. This nonemptiness condition is discharged by observing that for n ≥ 2, the glove number of K_n is at least 1 (by `glove_number_complete_graph_pos`); because the infimum of admissible glove counts is strictly positive, the set cannot be empty.
The equivalence glove_number(K_n) ≤ k ↔ has_clean_handshake_seq(K_n, k) holds provided that K_n has a clean handshake sequence for some number of gloves.
The lemma `glove_number_le_iff_has_clean_handshake_seq` reduces the desired if-and-only-if characterization to verifying that the set of admissible glove counts is nonempty, leaving the existential goal ∃ j, has_clean_handshake_seq(K_n, j).
uses
glove_number_le_iff_has_clean_handshake_seqapply glove_number_le_iff_has_clean_handshake_seqThere exists a glove count j for which K_n has a clean handshake sequence, completing the proof.
Since n ≥ 2, `glove_number_complete_graph_pos` shows that the glove number of K_n is at least 1. Unfolding the definition of `glove_number`, the infimum of the set of admissible glove counts is at least 1, which implies by linear arithmetic (`omega`) that the infimum is strictly positive. Finally, `Nat.nonempty_of_pos_sInf` concludes that this set of natural numbers is nonempty, providing the required witness j.
uses
glove_number_complete_graph_pos,glove_number,Nat.nonempty_of_pos_sInfhave h1 := glove_number_complete_graph_pos n hn simp only [glove_number] at h1 ⊢ have h : 0 < sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k} := by omega exact Nat.nonempty_of_pos_sInf h
glove_number_le_iff_has_clean_handshake_seq- For any graph G, if G has a clean handshake sequence for at least one number of gloves, then the glove number of G is at most k if and only if G has a clean handshake sequence with k gloves.
glove_number_complete_graph_pos- For n ≥ 2, the glove number of the complete graph K_n is at least 1.
glove_number- The glove number of a graph G is defined as the infimum of the set of natural numbers k for which G has a clean handshake sequence with k gloves.
Nat.nonempty_of_pos_sInf- If the infimum of a set of natural numbers is strictly greater than 0, then the set is nonempty.
- In Lean, the infimum `sInf` of the empty set of natural numbers is defined to be `0` (`Nat.sInf_empty`). Because of this convention, establishing that `sInf s > 0` suffices to deduce that `s ⊆ ℕ` is nonempty (`Nat.nonempty_of_pos_sInf`), whereas on paper the infimum of the empty set is typically considered undefined or $+\infty$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For `K_n`, `gl ≤ k` is equivalent to the existence of a `k`-glove covering sequence: no side condition is needed, because `gl(K_n) > 0` makes the set of admissible glove counts nonempty. -/theorem glove_number_complete_graph_le_iff (n : ℕ) (hn : 2 ≤ n) (k : ℕ) : glove_number (SimpleGraph.completeGraph (Fin n)) ≤ k ↔ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k := by apply glove_number_le_iff_has_clean_handshake_seq have h1 := glove_number_complete_graph_pos n hn simp only [glove_number] at h1 ⊢ have h : 0 < sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k} := by omega exact Nat.nonempty_of_pos_sInf h