AFTD Auto-Formalizing Theoretical Domains

glove_number_complete_graph_pos

theoremverified

For every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.

Statement

theorem glove_number_complete_graph_pos (n : ℕ) (hn : 2 ≤ n) :
    1 ≤ glove_number (SimpleGraph.completeGraph (Fin n))
Source
arXiv:2610.17602 Section 2 (Clean handshake sequences)
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • 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…
  • glove_number_complete_graph_no_zero_glovesFor any integer $n \ge 2$, there is no clean handshake sequence with zero gloves covering all edges of the complete graph $K_n$.
  • 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)$.
  • handshake_is_cleanA handshake is clean with respect to a contamination map $t : \Gamma \times \mathrm{Bool} \to \mathrm{Set}(V)$ if no player directly…
  • CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
  • HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
  • opp_glove_sideThe opposite side of a glove side $(g, b)$ in $\Gamma \times \mathrm{Bool}$ is $(g, \neg b)$, representing the inside-out orientation of…
  • handshake_update_contamThe updated contamination map after a handshake: players add their germs to the glove sides they touch directly, and in a double handshake…
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.

Read back from the Lean

For every natural number $n$ such that $2 \le n$, the glove number of the complete graph on vertex set Fin n is at least $1$ (i.e., $1 \le \text{glove\_number}(K_n)$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

dummy summary

  1. step 1

    explanation 1

    lines 1–7

    /-- A double handshake in which the first vertex wears the `false` side of glove `2 * φ p` and the
    second vertex wears the `false` side of glove `2 * φ p + 1`. -/
    def glove_number_complete_graph_pos_hs {ι V : Type*} (K : ℕ) (φ : ι → ℕ)
        (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι) : Handshake V (Fin K) :=
      Handshake.double (e p).1 (⟨2 * φ p, by have := hb p; omega⟩, false)
        (⟨2 * φ p + 1, by have := hb p; omega⟩, false) (e p).2
    
  2. step 2

    explanation 2

    lines 8–29

    uses glove_number_complete_graph_pos_hs, handshake_update_contam

    /-- The edge covered by such a double handshake. -/
    lemma glove_number_complete_graph_pos_hs_edge {ι V : Type*} (K : ℕ) (φ : ι → ℕ)
        (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι) :
        handshake_edge (glove_number_complete_graph_pos_hs K φ hb e p) = Sym2.mk (e p).1 (e p).2 :=
      rfl
    
    /-- The contamination update of such a handshake leaves untouched every glove side whose glove
    index differs from `2 * φ p` and `2 * φ p + 1`. -/
    lemma glove_number_complete_graph_pos_hs_update {ι V : Type*} (K : ℕ) (φ : ι → ℕ)
        (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι)
        (t : Fin K × Bool → Set V) (s : Fin K × Bool)
        (h1 : s.1.val ≠ 2 * φ p) (h2 : s.1.val ≠ 2 * φ p + 1) :
        handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t s = t s := by
      simp only [glove_number_complete_graph_pos_hs, handshake_update_contam]
      split_ifs with h h' h''
      · exact absurd (by rw [h]) h1
      · exact absurd (by rw [h']) h2
      · rcases h'' with h'' | h''
        · exact absurd (by rw [h'']; rfl) h1
        · exact absurd (by rw [h'']; rfl) h2
      · rfl
    
  3. step 3

    explanation 3

    lines 30–80

    /-- If the glove index map `φ` is injective and every glove side whose index is not among the
    already processed indices `P` is uncontaminated, then the sequence of fresh double handshakes
    along a duplicate-free list `L` disjoint from `P` is clean. -/
    lemma glove_number_complete_graph_pos_clean {ι V : Type*} (K : ℕ) (φ : ι → ℕ)
        (hφ : Function.Injective φ) (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V)
        (L P : List ι) (t : Fin K × Bool → Set V)
        (hL : L.Nodup) (hdisj : ∀ p ∈ L, p ∉ P)
        (hinv : ∀ s : Fin K × Bool, (∀ q ∈ P, s.1.val ≠ 2 * φ q ∧ s.1.val ≠ 2 * φ q + 1) → t s = ∅) :
        CleanHandshakeSeq (L.map (glove_number_complete_graph_pos_hs K φ hb e)) t := by
      induction L generalizing P t with
      | nil => exact CleanHandshakeSeq.nil t
      | cons p L ih =>
        obtain ⟨hpL, hL'⟩ := List.nodup_cons.mp hL
        have hpP : p ∉ P := hdisj p (List.mem_cons_self ..)
        have hkey : ∀ q ∈ P, 2 * φ p ≠ 2 * φ q ∧ 2 * φ p ≠ 2 * φ q + 1 := by
          intro q hq
          refine ⟨fun h => hpP ?_, fun h => by omega⟩
          have hpq : φ p = φ q := by omega
          rw [hφ hpq]; exact hq
        have hempty1 : t ((⟨2 * φ p, by have := hb p; omega⟩ : Fin K), false) = ∅ :=
          hinv _ hkey
        have hempty2 : t ((⟨2 * φ p + 1, by have := hb p; omega⟩ : Fin K), false) = ∅ := by
          refine hinv _ ?_
          intro q hq
          have hk := hkey q hq
          constructor
          · show 2 * φ p + 1 ≠ 2 * φ q
            omega
          · show 2 * φ p + 1 ≠ 2 * φ q + 1
            omega
        have hclean : handshake_is_clean (glove_number_complete_graph_pos_hs K φ hb e p) t := by
          refine ⟨?_, ?_, ?_⟩
          · intro h
            have hv : (2 : ℕ) * φ p = 2 * φ p + 1 := congrArg Fin.val h
            omega
          · rw [hempty1]; exact Set.empty_subset _
          · rw [hempty2]; exact Set.empty_subset _
        have hinv' : ∀ s : Fin K × Bool, (∀ q ∈ p :: P, s.1.val ≠ 2 * φ q ∧ s.1.val ≠ 2 * φ q + 1) →
            handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t s = ∅ := by
          intro s hs
          rw [glove_number_complete_graph_pos_hs_update K φ hb e p t s (hs p (List.mem_cons_self ..)).1
            (hs p (List.mem_cons_self ..)).2]
          exact hinv s (fun q hq => hs q (List.mem_cons_of_mem p hq))
        refine CleanHandshakeSeq.cons _ _ _ hclean ?_
        exact ih (p :: P) (handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t) hL'
          (fun q hq => by
            intro hq2
            rcases List.mem_cons.mp hq2 with rfl | hq2'
            · exact hpL hq
            · exact hdisj q (List.mem_cons_of_mem p hq) hq2') hinv'
    
  4. step 4

    explanation 4

    lines 81–129

    /-- For n ≥ 2, the glove number of K_n is at least 1. -/
    theorem glove_number_complete_graph_pos (n : ℕ) (hn : 2 ≤ n) :
        1 ≤ glove_number (SimpleGraph.completeGraph (Fin n)) := by
      have hn0 : 0 < n := by omega
      have hex : ∃ k, has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k := by
        let φ : Fin (n * n) → ℕ := fun k => k.val
        have hφ : Function.Injective φ := fun a b h => Fin.ext h
        have hb : ∀ k : Fin (n * n), 2 * φ k + 1 < 2 * (n * n) := by
          intro k
          have := k.isLt
          simp only [φ]
          omega
        let e : Fin (n * n) → Fin n × Fin n := fun k =>
          (⟨k.val / n, (Nat.div_lt_iff_lt_mul hn0).mpr k.isLt⟩, ⟨k.val % n, Nat.mod_lt _ hn0⟩)
        have hclean := glove_number_complete_graph_pos_clean (K := 2 * (n * n)) (φ := φ) hφ hb e
          (List.finRange (n * n)) [] (fun _ => ∅) (List.nodup_finRange _) (by simp) (by simp)
        refine ⟨2 * (n * n), List.map (glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e)
          (List.finRange (n * n)), hclean, ?_⟩
        have hk' : ∀ i j : Fin n, i.val * n + j.val < n * n := by
          intro i j
          have h1 : i.val * n + j.val < (i.val + 1) * n := by
            rw [Nat.add_mul, Nat.one_mul]
            omega
          exact lt_of_lt_of_le h1 (Nat.mul_le_mul_right n (Nat.succ_le_of_lt i.isLt))
        have key : ∀ i j : Fin n, Sym2.mk i j ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet →
            ∃ h ∈ List.map (glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e)
              (List.finRange (n * n)), handshake_edge h = Sym2.mk i j := by
          intro i j _
          have hdiv : (i.val * n + j.val) / n = i.val := by
            have h1 : i.val * n + j.val = j.val + n * i.val := by rw [Nat.mul_comm i.val n]; omega
            rw [h1, Nat.add_mul_div_left j.val i.val hn0, Nat.div_eq_of_lt j.isLt, Nat.zero_add]
          have hmod : (i.val * n + j.val) % n = j.val := by
            rw [Nat.mul_comm i.val n, Nat.mul_add_mod_self_left, Nat.mod_eq_of_lt j.isLt]
          have hek : e ⟨i.val * n + j.val, hk' i j⟩ = (i, j) := by
            simp only [e, hdiv, hmod]
          refine ⟨glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e ⟨i.val * n + j.val, hk' i j⟩,
            List.mem_map.mpr ⟨_, List.mem_finRange _, rfl⟩, ?_⟩
          rw [glove_number_complete_graph_pos_hs_edge, hek]
        intro edge hedge
        exact Sym2.ind key edge hedge
      have hne : {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k}.Nonempty := hex
      have hpos : sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k} ≠ 0 := by
        intro h
        rcases Nat.sInf_eq_zero.mp h with h0 | hemp
        · exact glove_number_complete_graph_no_zero_gloves n hn h0
        · rw [hemp] at hne
          exact Set.not_nonempty_empty hne
      show 1 ≤ sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k}
      omega

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

/-- A double handshake in which the first vertex wears the `false` side of glove `2 * φ p` and thesecond vertex wears the `false` side of glove `2 * φ p + 1`. -/def glove_number_complete_graph_pos_hs {ι V : Type*} (K : ℕ) (φ : ι → ℕ)    (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι) : Handshake V (Fin K) :=  Handshake.double (e p).1 (⟨2 * φ p, by have := hb p; omega⟩, false)    (⟨2 * φ p + 1, by have := hb p; omega⟩, false) (e p).2/-- The edge covered by such a double handshake. -/lemma glove_number_complete_graph_pos_hs_edge {ι V : Type*} (K : ℕ) (φ : ι → ℕ)    (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι) :    handshake_edge (glove_number_complete_graph_pos_hs K φ hb e p) = Sym2.mk (e p).1 (e p).2 :=  rfl/-- The contamination update of such a handshake leaves untouched every glove side whose gloveindex differs from `2 * φ p` and `2 * φ p + 1`. -/lemma glove_number_complete_graph_pos_hs_update {ι V : Type*} (K : ℕ) (φ : ι → ℕ)    (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V) (p : ι)    (t : Fin K × Bool → Set V) (s : Fin K × Bool)    (h1 : s.1.val ≠ 2 * φ p) (h2 : s.1.val ≠ 2 * φ p + 1) :    handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t s = t s := by  simp only [glove_number_complete_graph_pos_hs, handshake_update_contam]  split_ifs with h h' h''  · exact absurd (by rw [h]) h1  · exact absurd (by rw [h']) h2  · rcases h'' with h'' | h''    · exact absurd (by rw [h'']; rfl) h1    · exact absurd (by rw [h'']; rfl) h2  · rfl/-- If the glove index map `φ` is injective and every glove side whose index is not among thealready processed indices `P` is uncontaminated, then the sequence of fresh double handshakesalong a duplicate-free list `L` disjoint from `P` is clean. -/lemma glove_number_complete_graph_pos_clean {ι V : Type*} (K : ℕ) (φ : ι → ℕ)    (hφ : Function.Injective φ) (hb : ∀ p, 2 * φ p + 1 < K) (e : ι → V × V)    (L P : List ι) (t : Fin K × Bool → Set V)    (hL : L.Nodup) (hdisj : ∀ p ∈ L, p ∉ P)    (hinv : ∀ s : Fin K × Bool, (∀ q ∈ P, s.1.val ≠ 2 * φ q ∧ s.1.val ≠ 2 * φ q + 1) → t s = ∅) :    CleanHandshakeSeq (L.map (glove_number_complete_graph_pos_hs K φ hb e)) t := by  induction L generalizing P t with  | nil => exact CleanHandshakeSeq.nil t  | cons p L ih =>    obtain ⟨hpL, hL'⟩ := List.nodup_cons.mp hL    have hpP : p ∉ P := hdisj p (List.mem_cons_self ..)    have hkey : ∀ q ∈ P, 2 * φ p ≠ 2 * φ q ∧ 2 * φ p ≠ 2 * φ q + 1 := by      intro q hq      refine ⟨fun h => hpP ?_, fun h => by omega⟩      have hpq : φ p = φ q := by omega      rw [hφ hpq]; exact hq    have hempty1 : t ((⟨2 * φ p, by have := hb p; omega⟩ : Fin K), false) = ∅ :=      hinv _ hkey    have hempty2 : t ((⟨2 * φ p + 1, by have := hb p; omega⟩ : Fin K), false) = ∅ := by      refine hinv _ ?_      intro q hq      have hk := hkey q hq      constructor      · show 2 * φ p + 1 ≠ 2 * φ q        omega      · show 2 * φ p + 1 ≠ 2 * φ q + 1        omega    have hclean : handshake_is_clean (glove_number_complete_graph_pos_hs K φ hb e p) t := by      refine ⟨?_, ?_, ?_⟩      · intro h        have hv : (2 : ℕ) * φ p = 2 * φ p + 1 := congrArg Fin.val h        omega      · rw [hempty1]; exact Set.empty_subset _      · rw [hempty2]; exact Set.empty_subset _    have hinv' : ∀ s : Fin K × Bool, (∀ q ∈ p :: P, s.1.val ≠ 2 * φ q ∧ s.1.val ≠ 2 * φ q + 1) →        handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t s = ∅ := by      intro s hs      rw [glove_number_complete_graph_pos_hs_update K φ hb e p t s (hs p (List.mem_cons_self ..)).1        (hs p (List.mem_cons_self ..)).2]      exact hinv s (fun q hq => hs q (List.mem_cons_of_mem p hq))    refine CleanHandshakeSeq.cons _ _ _ hclean ?_    exact ih (p :: P) (handshake_update_contam (glove_number_complete_graph_pos_hs K φ hb e p) t) hL'      (fun q hq => by        intro hq2        rcases List.mem_cons.mp hq2 with rfl | hq2'        · exact hpL hq        · exact hdisj q (List.mem_cons_of_mem p hq) hq2') hinv'/-- For n ≥ 2, the glove number of K_n is at least 1. -/theorem glove_number_complete_graph_pos (n : ℕ) (hn : 2 ≤ n) :    1 ≤ glove_number (SimpleGraph.completeGraph (Fin n)) := by  have hn0 : 0 < n := by omega  have hex : ∃ k, has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k := by    let φ : Fin (n * n) → ℕ := fun k => k.val    have hφ : Function.Injective φ := fun a b h => Fin.ext h    have hb : ∀ k : Fin (n * n), 2 * φ k + 1 < 2 * (n * n) := by      intro k      have := k.isLt      simp only [φ]      omega    let e : Fin (n * n) → Fin n × Fin n := fun k =>      (⟨k.val / n, (Nat.div_lt_iff_lt_mul hn0).mpr k.isLt⟩, ⟨k.val % n, Nat.mod_lt _ hn0⟩)    have hclean := glove_number_complete_graph_pos_clean (K := 2 * (n * n)) (φ := φ) hφ hb e      (List.finRange (n * n)) [] (fun _ => ∅) (List.nodup_finRange _) (by simp) (by simp)    refine ⟨2 * (n * n), List.map (glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e)      (List.finRange (n * n)), hclean, ?_⟩    have hk' : ∀ i j : Fin n, i.val * n + j.val < n * n := by      intro i j      have h1 : i.val * n + j.val < (i.val + 1) * n := by        rw [Nat.add_mul, Nat.one_mul]        omega      exact lt_of_lt_of_le h1 (Nat.mul_le_mul_right n (Nat.succ_le_of_lt i.isLt))    have key : ∀ i j : Fin n, Sym2.mk i j ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet →        ∃ h ∈ List.map (glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e)          (List.finRange (n * n)), handshake_edge h = Sym2.mk i j := by      intro i j _      have hdiv : (i.val * n + j.val) / n = i.val := by        have h1 : i.val * n + j.val = j.val + n * i.val := by rw [Nat.mul_comm i.val n]; omega        rw [h1, Nat.add_mul_div_left j.val i.val hn0, Nat.div_eq_of_lt j.isLt, Nat.zero_add]      have hmod : (i.val * n + j.val) % n = j.val := by        rw [Nat.mul_comm i.val n, Nat.mul_add_mod_self_left, Nat.mod_eq_of_lt j.isLt]      have hek : e ⟨i.val * n + j.val, hk' i j⟩ = (i, j) := by        simp only [e, hdiv, hmod]      refine ⟨glove_number_complete_graph_pos_hs (2 * (n * n)) φ hb e ⟨i.val * n + j.val, hk' i j⟩,        List.mem_map.mpr ⟨_, List.mem_finRange _, rfl⟩, ?_⟩      rw [glove_number_complete_graph_pos_hs_edge, hek]    intro edge hedge    exact Sym2.ind key edge hedge  have hne : {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k}.Nonempty := hex  have hpos : sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k} ≠ 0 := by    intro h    rcases Nat.sInf_eq_zero.mp h with h0 | hemp    · exact glove_number_complete_graph_no_zero_gloves n hn h0    · rw [hemp] at hne      exact Set.not_nonempty_empty hne  show 1 ≤ sInf {k | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) k}  omega
See it in the graphDiscuss this resultChallenge it