glove_number_k3
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
- glove_number_complete_graph_le_threeFor any integer $n$ such that $2 \\le n \\le 3$, the glove number of the complete graph $K_n$ is equal to $n - 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₃.
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.
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]
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.
uses
congrArg,Prod.sndintro h1 have := congrArg Prod.snd h1 simp [opp_glove_side] at this
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.
simp [opp_glove_side]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}.
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.elimhave 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
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.
uses
List.not_mem_nil,glove_number_k3_clean_step,List.mem_cons.mpintro 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
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).
uses
List.not_mem_nil,glove_number_k3_opp_ne,List.mem_cons.mp,glove_number_k3_edges_eq,Subsingleton.elimintro 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
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.
uses
glove_number_k3_all_edges_same,SimpleGraph.mem_edgeSetrintro ⟨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)
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₃.
uses
SimpleGraph.mem_edgeSet,List.not_mem_nilrintro ⟨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₃ 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.
uses
le_antisymm,glove_number_complete_graph_upper_boundapply le_antisymm · simpa using glove_number_complete_graph_upper_bound 3 (by norm_num)
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).
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.
- In Step 7, the inequality of edges s(0, 1) ≠ s(1, 2) in Sym2 (Fin 3) is discharged by computational reflection (`decide`).
- In Step 8, the impossibility of any handshake with 0 gloves is formalized by `elim0` on the empty type Fin 0.
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.
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