AFTD Auto-Formalizing Theoretical Domains

glove_number_complete_graph_le_iff

theoremverified

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

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.

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

    line 5

    uses glove_number_le_iff_has_clean_handshake_seq

      apply glove_number_le_iff_has_clean_handshake_seq
  2. There 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.

    lines 6–9

    uses glove_number_complete_graph_pos, glove_number, Nat.nonempty_of_pos_sInf

      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
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.

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