AFTD Auto-Formalizing Theoretical Domains

glove_number_k3

theoremverifiedformalization

The glove number of the complete graph $K_3$ is equal to 2.

Statement

theorem glove_number_k3 : glove_number (SimpleGraph.completeGraph (Fin 3)) = 2
Formalizes
scout/2610-17602-clean-handshake-sequences.md:348
Verified
18 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…
  • 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…
  • 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…
  • CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
  • 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…
  • glove_number_complete_graph_upper_boundFor all integers $n \ge 2$, the glove number of the complete graph $K_n$ is at most $n - 1$.
  • handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
  • 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

Read back from the Lean

The glove number of the complete graph on 3 vertices (SimpleGraph.completeGraph (Fin 3)) is equal to 2; that is, the minimum number of gloves k : ℕ needed to execute a clean sequence of handshakes covering every edge of K₃ is 2.

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

The glove number of the complete graph K₃ is proved to be 2 by establishing matching upper and lower bounds. The upper bound follows from the general bound for complete graphs, giving glove_number(K₃) ≤ 3 - 1 = 2. For the lower bound, 0 gloves is impossible because no handshakes can be formed to cover any edges. With 1 glove, double handshakes are impossible because only one glove exists, and once the sole glove is used in the first handshake, both sides are contaminated with distinct vertices; every subsequent clean handshake is forced to reuse the exact same edge, making it impossible to cover more than one of the three edges of K₃.

  1. For any two glove sides a, b ∈ Fin 1 × Bool, either b = a or b = opp_glove_side a.

    Since Fin 1 has a single element 0, the glove indices of a and b are necessarily equal. A case analysis on the boolean components of a and b then shows that b is either identical to a or is its boolean flip, which by definition is opp_glove_side a.

    lines 2–6

      obtain ⟨⟨u, hu⟩, bb⟩ := a
      obtain ⟨⟨u', hu'⟩, bb'⟩ := b
      have hu2 : u = u' := by omega
      subst hu2
      rcases bb with _ | _ <;> rcases bb' with _ | _ <;> simp [opp_glove_side]
  2. A glove side a is never equal to its opposite side opp_glove_side a.

    Assuming opp_glove_side a = a, applying Prod.snd via congrArg yields that the boolean component equals its own negation, which is a contradiction.

    lines 9–11

    uses congrArg, Prod.snd

      intro h1
      have := congrArg Prod.snd h1
      simp [opp_glove_side] at this
  3. Inverting the glove side twice returns the original side: opp_glove_side (opp_glove_side a) = a.

    By definition of opp_glove_side, the glove index is unchanged and the boolean component is negated twice, which simplifies to the original pair.

    line 14

      simp [opp_glove_side]
  4. In a 1-glove system where side a is contaminated by {p} and its opposite by {q}, any clean handshake covers edge s(p, q) and preserves these contaminations.

    First, double handshakes are impossible because Fin 1 has only one glove index, so the two distinct glove indices required by a double handshake cannot exist (Subsingleton.elim). For a single handshake using side b, by glove_number_k3_cover, either b = a or b = opp_glove_side a. In the first case, the cleanliness condition implies the participants must be p and q, so the edge is s(p, q), and updating the contaminations leaves {p} and {q} unchanged. In the second case, the participants are q and p, producing the symmetric edge s(q, p) = s(p, q) by Sym2.eq_swap, and updating again leaves the contaminations as {p} and {q}.

    lines 23–41

    uses glove_number_k3_opp_opp, glove_number_k3_opp_ne, glove_number_k3_cover, Set.singleton_subset_iff, Sym2.eq_swap, Ne.symm, Subsingleton.elim

      have hoo := glove_number_k3_opp_opp a
      have hone := glove_number_k3_opp_ne a
      cases h with
      | single x b y =>
        rcases glove_number_k3_cover a b with rfl | rfl
        · obtain ⟨h1, h2⟩ := hc
          rw [ha, Set.singleton_subset_iff] at h1
          rw [hb, Set.singleton_subset_iff] at h2
          subst h1; subst h2
          exact ⟨rfl, by simp [handshake_update_contam, ha],
            by simp [handshake_update_contam, hb, hone]⟩
        · obtain ⟨h1, h2⟩ := hc
          rw [hb, Set.singleton_subset_iff] at h1
          rw [hoo, ha, Set.singleton_subset_iff] at h2
          subst h1; subst h2
          exact ⟨Sym2.eq_swap, by simp [handshake_update_contam, ha, hoo, Ne.symm hone],
            by simp [handshake_update_contam, hb]⟩
      | double x b1 b2 y =>
        exact absurd (Subsingleton.elim b1.1 b2.1) hc.1
  5. If side a has contamination {p} and its opposite has {q}, every handshake in a clean sequence covers edge s(p, q).

    By induction on the handshake sequence. The base case of an empty sequence is vacuous. For the inductive step, glove_number_k3_clean_step shows that the head handshake covers edge s(p, q) and preserves the contamination state {p} and {q}. The induction hypothesis then applies to the rest of the sequence.

    lines 47–58

    uses List.not_mem_nil, glove_number_k3_clean_step, List.mem_cons.mp

      intro seq
      induction seq with
      | nil => intro t ha hb hc h hh; exact absurd hh List.not_mem_nil
      | cons hd tl ih =>
        intro t ha hb hc
        cases hc with
        | cons _ _ t' hcle hrest =>
          have hstep := glove_number_k3_clean_step a p q t ha hb hd hcle
          intro h hh
          rcases List.mem_cons.mp hh with rfl | hh
          · exact hstep.1
          · exact ih (handshake_update_contam hd t) hstep.2.1 hstep.2.2 hrest h hh
  6. In any clean handshake sequence on Fin 3 with 1 glove starting from clean gloves, all handshakes cover the exact same edge e.

    If the sequence is empty, the claim holds vacuously. If non-empty, the first handshake cannot be double (by Subsingleton.elim) and must therefore be a single handshake on some edge s(x, y). This initial handshake contaminates side a with {x} and its opposite with {y}. By glove_number_k3_edges_eq, all subsequent handshakes in the sequence must also cover the edge s(x, y).

    lines 64–84

    uses List.not_mem_nil, glove_number_k3_opp_ne, List.mem_cons.mp, glove_number_k3_edges_eq, Subsingleton.elim

      intro seq hclean
      rcases seq with _ | ⟨hd, tl⟩
      · exact ⟨s(0, 1), by intro h hh; exact absurd hh List.not_mem_nil⟩
      · cases hclean with
        | cons _ _ _ hc hrest =>
          cases hd with
          | single x a y =>
            refine ⟨s(x, y), ?_⟩
            have hone := glove_number_k3_opp_ne a
            have ht1 : (handshake_update_contam (Handshake.single x a y)
                (fun _ => (∅ : Set (Fin 3)))) a = {x} := by
              simp [handshake_update_contam]
            have ht2 : (handshake_update_contam (Handshake.single x a y)
                (fun _ => (∅ : Set (Fin 3)))) (opp_glove_side a) = {y} := by
              simp [handshake_update_contam, hone]
            intro h hh
            rcases List.mem_cons.mp hh with rfl | hh
            · rfl
            · exact glove_number_k3_edges_eq a x y tl _ ht1 ht2 hrest h hh
          | double x b1 b2 y =>
            exact absurd (Subsingleton.elim b1.1 b2.1) hc.1
  7. The complete graph K₃ does not admit a clean handshake sequence using 1 glove.

    Suppose for contradiction that such a sequence exists. By glove_number_k3_all_edges_same, every handshake in the sequence must cover the same edge e. However, the sequence must cover all edges of K₃, including s(0, 1) and s(1, 2). Hence both s(0, 1) = e and s(1, 2) = e, implying s(0, 1) = s(1, 2), which is false.

    lines 88–98

    uses glove_number_k3_all_edges_same, SimpleGraph.mem_edgeSet

      rintro ⟨seq, hclean, hcover⟩
      obtain ⟨e, he⟩ := glove_number_k3_all_edges_same seq hclean
      have hedge1 : s((0:Fin 3), (1:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by
        rw [SimpleGraph.mem_edgeSet]; simp
      have hedge2 : s((1:Fin 3), (2:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by
        rw [SimpleGraph.mem_edgeSet]; simp
      obtain ⟨h1, h1mem, h1e⟩ := hcover _ hedge1
      obtain ⟨h2, h2mem, h2e⟩ := hcover _ hedge2
      have he1 : s(0, 1) = e := by rw [← h1e, he h1 h1mem]
      have he2 : s(1, 2) = e := by rw [← h2e, he h2 h2mem]
      exact absurd (he1.trans he2.symm) (by decide)
  8. The complete graph K₃ does not admit a clean handshake sequence using 0 gloves.

    With 0 gloves, no handshakes can be formed because Fin 0 is empty, so any sequence must be empty. But an empty sequence cannot cover the edge s(0, 1) of K₃.

    lines 102–114

    uses SimpleGraph.mem_edgeSet, List.not_mem_nil

      rintro ⟨seq, hclean, hcover⟩
      have hempty : seq = [] := by
        rcases seq with _ | ⟨hd, tl⟩
        · rfl
        · exfalso
          cases hd with
          | single x a y => exact a.1.elim0
          | double x a b y => exact a.1.elim0
      have hedge1 : s((0:Fin 3), (1:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by
        rw [SimpleGraph.mem_edgeSet]; simp
      obtain ⟨h, hh, -⟩ := hcover _ hedge1
      rw [hempty] at hh
      exact absurd hh List.not_mem_nil
  9. The glove number of K₃ is at most 2.

    By glove_number_complete_graph_upper_bound applied with n = 3, since 2 ≤ 3, the glove number of the complete graph on 3 vertices is at most 3 - 1 = 2.

    lines 118–119

    uses le_antisymm, glove_number_complete_graph_upper_bound

      apply le_antisymm
      · simpa using glove_number_complete_graph_upper_bound 3 (by norm_num)
  10. The glove number of K₃ is equal to 2.

    Unfolding the definition of glove_number as the infimum of glove counts admitting a clean handshake sequence, the set is non-empty because k = 2 admits such a sequence (by glove_number_complete_graph_upper_bound_has_clean_seq). Thus the infimum belongs to the set by Nat.sInf_mem. But the infimum cannot be 0 (by glove_number_k3_no_zero) nor 1 (by glove_number_k3_no_one). Since the infimum is at most 2 and not 0 or 1, it must be 2 by linear integer arithmetic (omega).

    lines 120–130

    uses glove_number_complete_graph_upper_bound_has_clean_seq, Nat.sInf_mem, glove_number_k3_no_zero, glove_number_k3_no_one

      · unfold glove_number
        have h2 : has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) 2 :=
          glove_number_complete_graph_upper_bound_has_clean_seq 2
        have hmem : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ∈
            {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} :=
          Nat.sInf_mem ⟨2, h2⟩
        have h0 : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ≠ 0 :=
          fun hc => glove_number_k3_no_zero (hc ▸ hmem)
        have h1 : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ≠ 1 :=
          fun hc => glove_number_k3_no_one (hc ▸ hmem)
        omega
congrArg
If a₁ = a₂, then f a₁ = f a₂ for any function f.
Prod.snd
The projection mapping an ordered pair to its second component.
glove_number_k3_cover
For any two glove sides a, b in Fin 1 × Bool, either b = a or b is the opposite side opp_glove_side a.
glove_number_k3_opp_ne
A glove side a in Fin 1 × Bool is never equal to its opposite side opp_glove_side a.
glove_number_k3_opp_opp
Inverting the glove side twice returns the original side: opp_glove_side (opp_glove_side a) = a.
glove_number_k3_clean_step
In a 1-glove system where side a has contamination {p} and its opposite has {q}, any clean handshake covers edge s(p, q) and preserves both contaminations.
Set.singleton_subset_iff
A singleton set {a} is a subset of s if and only if a ∈ s.
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
glove_number_k3_edges_eq
If a 1-glove system has side a contaminated by {p} and its opposite by {q}, then every handshake in a clean handshake sequence covers edge s(p, q).
List.not_mem_nil
No element belongs to the empty list.
List.mem_cons.mp
If an element is in hd :: tl, then it equals hd or belongs to tl.
glove_number_k3_all_edges_same
In any clean handshake sequence on Fin 3 with 1 glove starting from clean gloves, all handshakes cover the exact same edge.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) is in the edge set of graph G if and only if v and w are adjacent in G.
glove_number_k3_no_one
The complete graph K₃ has no clean handshake sequence using 1 glove.
glove_number_k3_no_zero
The complete graph K₃ has no clean handshake sequence using 0 gloves.
le_antisymm
If a ≤ b and b ≤ a, then a = b in a partial order.
glove_number_complete_graph_upper_bound
For any n ≥ 2, the glove number of the complete graph K_n is at most n - 1.
glove_number_complete_graph_upper_bound_has_clean_seq
For any natural number m, the complete graph K_{m+1} admits a clean handshake sequence using m gloves.
Nat.sInf_mem
If a set of natural numbers is non-empty, its infimum belongs to the set.

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

lemma glove_number_k3_cover (a b : Fin 1 × Bool) : b = a ∨ b = opp_glove_side a := by  obtain ⟨⟨u, hu⟩, bb⟩ := a  obtain ⟨⟨u', hu'⟩, bb'⟩ := b  have hu2 : u = u' := by omega  subst hu2  rcases bb with _ | _ <;> rcases bb' with _ | _ <;> simp [opp_glove_side]lemma glove_number_k3_opp_ne (a : Fin 1 × Bool) : opp_glove_side a ≠ a := by  intro h1  have := congrArg Prod.snd h1  simp [opp_glove_side] at thislemma glove_number_k3_opp_opp (a : Fin 1 × Bool) : opp_glove_side (opp_glove_side a) = a := by  simp [opp_glove_side]lemma glove_number_k3_clean_step {V : Type*} (a : Fin 1 × Bool) (p q : V)    (t : Fin 1 × Bool → Set V)    (ha : t a = {p}) (hb : t (opp_glove_side a) = {q})    (h : Handshake V (Fin 1)) (hc : handshake_is_clean h t) :    handshake_edge h = s(p, q) ∧      (handshake_update_contam h t) a = {p} ∧      (handshake_update_contam h t) (opp_glove_side a) = {q} := by  have hoo := glove_number_k3_opp_opp a  have hone := glove_number_k3_opp_ne a  cases h with  | single x b y =>    rcases glove_number_k3_cover a b with rfl | rfl    · obtain ⟨h1, h2⟩ := hc      rw [ha, Set.singleton_subset_iff] at h1      rw [hb, Set.singleton_subset_iff] at h2      subst h1; subst h2      exact ⟨rfl, by simp [handshake_update_contam, ha],        by simp [handshake_update_contam, hb, hone]⟩    · obtain ⟨h1, h2⟩ := hc      rw [hb, Set.singleton_subset_iff] at h1      rw [hoo, ha, Set.singleton_subset_iff] at h2      subst h1; subst h2      exact ⟨Sym2.eq_swap, by simp [handshake_update_contam, ha, hoo, Ne.symm hone],        by simp [handshake_update_contam, hb]⟩  | double x b1 b2 y =>    exact absurd (Subsingleton.elim b1.1 b2.1) hc.1lemma glove_number_k3_edges_eq {V : Type*} (a : Fin 1 × Bool) (p q : V) :    ∀ (seq : List (Handshake V (Fin 1))) (t : Fin 1 × Bool → Set V),      t a = {p} → t (opp_glove_side a) = {q} → CleanHandshakeSeq seq t →      ∀ h ∈ seq, handshake_edge h = s(p, q) := by  intro seq  induction seq with  | nil => intro t ha hb hc h hh; exact absurd hh List.not_mem_nil  | cons hd tl ih =>    intro t ha hb hc    cases hc with    | cons _ _ t' hcle hrest =>      have hstep := glove_number_k3_clean_step a p q t ha hb hd hcle      intro h hh      rcases List.mem_cons.mp hh with rfl | hh      · exact hstep.1      · exact ih (handshake_update_contam hd t) hstep.2.1 hstep.2.2 hrest h hhlemma glove_number_k3_all_edges_same :    ∀ seq : List (Handshake (Fin 3) (Fin 1)),      CleanHandshakeSeq seq (fun _ => (∅ : Set (Fin 3))) →      ∃ e : Sym2 (Fin 3), ∀ h ∈ seq, handshake_edge h = e := by  intro seq hclean  rcases seq with _ | ⟨hd, tl⟩  · exact ⟨s(0, 1), by intro h hh; exact absurd hh List.not_mem_nil⟩  · cases hclean with    | cons _ _ _ hc hrest =>      cases hd with      | single x a y =>        refine ⟨s(x, y), ?_⟩        have hone := glove_number_k3_opp_ne a        have ht1 : (handshake_update_contam (Handshake.single x a y)            (fun _ => (∅ : Set (Fin 3)))) a = {x} := by          simp [handshake_update_contam]        have ht2 : (handshake_update_contam (Handshake.single x a y)            (fun _ => (∅ : Set (Fin 3)))) (opp_glove_side a) = {y} := by          simp [handshake_update_contam, hone]        intro h hh        rcases List.mem_cons.mp hh with rfl | hh        · rfl        · exact glove_number_k3_edges_eq a x y tl _ ht1 ht2 hrest h hh      | double x b1 b2 y =>        exact absurd (Subsingleton.elim b1.1 b2.1) hc.1lemma glove_number_k3_no_one :    ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) 1 := by  rintro ⟨seq, hclean, hcover⟩  obtain ⟨e, he⟩ := glove_number_k3_all_edges_same seq hclean  have hedge1 : s((0:Fin 3), (1:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by    rw [SimpleGraph.mem_edgeSet]; simp  have hedge2 : s((1:Fin 3), (2:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by    rw [SimpleGraph.mem_edgeSet]; simp  obtain ⟨h1, h1mem, h1e⟩ := hcover _ hedge1  obtain ⟨h2, h2mem, h2e⟩ := hcover _ hedge2  have he1 : s(0, 1) = e := by rw [← h1e, he h1 h1mem]  have he2 : s(1, 2) = e := by rw [← h2e, he h2 h2mem]  exact absurd (he1.trans he2.symm) (by decide)lemma glove_number_k3_no_zero :    ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) 0 := by  rintro ⟨seq, hclean, hcover⟩  have hempty : seq = [] := by    rcases seq with _ | ⟨hd, tl⟩    · rfl    · exfalso      cases hd with      | single x a y => exact a.1.elim0      | double x a b y => exact a.1.elim0  have hedge1 : s((0:Fin 3), (1:Fin 3)) ∈ (SimpleGraph.completeGraph (Fin 3)).edgeSet := by    rw [SimpleGraph.mem_edgeSet]; simp  obtain ⟨h, hh, -⟩ := hcover _ hedge1  rw [hempty] at hh  exact absurd hh List.not_mem_nil/-- The glove number of K_3 is 2. -/theorem glove_number_k3 : glove_number (SimpleGraph.completeGraph (Fin 3)) = 2 := by  apply le_antisymm  · simpa using glove_number_complete_graph_upper_bound 3 (by norm_num)  · unfold glove_number    have h2 : has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) 2 :=      glove_number_complete_graph_upper_bound_has_clean_seq 2    have hmem : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ∈        {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} :=      Nat.sInf_mem ⟨2, h2⟩    have h0 : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ≠ 0 :=      fun hc => glove_number_k3_no_zero (hc ▸ hmem)    have h1 : sInf {k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 3)) k} ≠ 1 :=      fun hc => glove_number_k3_no_one (hc ▸ hmem)    omega
See it in the graphDiscuss this resultChallenge it