glove_number_le_iff_has_clean_handshake_seq
If 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 clean handshake sequence with $k$ gloves.
Statement
theorem glove_number_le_iff_has_clean_handshake_seq {V : Type*} (G : SimpleGraph V) (hne : ∃ j, has_clean_handshake_seq G j) (k : ℕ) : glove_number G ≤ k ↔ has_clean_handshake_seq G k
- Source
- step towards glove_number_complete_graph_open_problem
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- has_clean_handshake_seq_monoIf a graph $G$ admits a clean handshake sequence with $k$ gloves and $k \le k'$, then it admits one with $k'$ gloves.
- 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…
- 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 1
- 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.
The proof, explained
The glove number of G is defined as the infimum of the set of natural numbers j for which G admits a clean handshake sequence with j gloves. Because this property is upward-closed (monotonic) in the number of gloves and the set is nonempty by assumption, the set of admissible glove counts is precisely the closed interval starting at the glove number. Consequently, glove_number G ≤ k is equivalent to k belonging to this set, which means G has a clean handshake sequence with k gloves.
The set of glove counts for which G has a clean handshake sequence is the closed interval [glove_number G, ∞).
By definition, `glove_number G` is the infimum of the set S = {j : ℕ | has_clean_handshake_seq G j}. Because S is nonempty by assumption (hne) and upward-closed by the monotonicity lemma `has_clean_handshake_seq_mono`, `Nat.eq_Ici_of_nonempty_of_upward_closed` identifies S with the interval [sInf S, ∞), which is [glove_number G, ∞).
uses
Nat.eq_Ici_of_nonempty_of_upward_closed,has_clean_handshake_seq_monohave hS : {j : ℕ | has_clean_handshake_seq G j} = Set.Ici (glove_number G) := by show {j : ℕ | has_clean_handshake_seq G j} = Set.Ici (sInf {j : ℕ | has_clean_handshake_seq G j}) exact Nat.eq_Ici_of_nonempty_of_upward_closed hne (fun k₁ k₂ hkk hk => has_clean_handshake_seq_mono G hkk hk)
glove_number G ≤ k if and only if G has a clean handshake sequence with k gloves.
By `Set.mem_Ici`, the condition glove_number G ≤ k is equivalent to k ∈ [glove_number G, ∞). Using the equality hS established in the first step, this interval is rewritten to the set of feasible glove counts {j : ℕ | has_clean_handshake_seq G j}. Finally, testing membership of k in this set is definitionally has_clean_handshake_seq G k, concluding the proof by reflexivity (`rfl`).
uses
Set.mem_Icirw [← Set.mem_Ici, ← hS] rfl
Nat.eq_Ici_of_nonempty_of_upward_closed- A nonempty, upward-closed subset of ℕ is equal to the upper interval [sInf s, ∞).
has_clean_handshake_seq_mono- If a graph has a clean handshake sequence with k gloves and k ≤ k', it also has a clean handshake sequence with k' gloves.
Set.mem_Ici- An element x belongs to the upper interval [b, ∞) if and only if b ≤ x.
- In Lean, the infimum `sInf` on `ℕ` defaults to 0 when the set is empty, which is why the hypothesis `hne` asserting the existence of at least one valid sequence is needed to apply `Nat.eq_Ici_of_nonempty_of_upward_closed`.
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 a graph some number of gloves suffices for, having at most `k` gloves is the same as having a `k`-glove covering sequence. -/theorem glove_number_le_iff_has_clean_handshake_seq {V : Type*} (G : SimpleGraph V) (hne : ∃ j, has_clean_handshake_seq G j) (k : ℕ) : glove_number G ≤ k ↔ has_clean_handshake_seq G k := by have hS : {j : ℕ | has_clean_handshake_seq G j} = Set.Ici (glove_number G) := by show {j : ℕ | has_clean_handshake_seq G j} = Set.Ici (sInf {j : ℕ | has_clean_handshake_seq G j}) exact Nat.eq_Ici_of_nonempty_of_upward_closed hne (fun k₁ k₂ hkk hk => has_clean_handshake_seq_mono G hkk hk) rw [← Set.mem_Ici, ← hS] rfl