AFTD Auto-Formalizing Theoretical Domains

glove_number_le_iff_has_clean_handshake_seq

theoremverified

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.

  1. 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, ∞).

    lines 5–9

    uses Nat.eq_Ici_of_nonempty_of_upward_closed, has_clean_handshake_seq_mono

      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)
  2. 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`).

    lines 10–11

    uses Set.mem_Ici

      rw [← 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.

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

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