glove_number_k2
The glove number of the complete graph $K_2$ is equal to 1.
Statement
theorem glove_number_k2 : glove_number (SimpleGraph.completeGraph (Fin 2)) = 1- Formalizes
- scout/2610-17602-clean-handshake-sequences.md:348
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_upper_boundFor all integers $n \ge 2$, the glove number of the complete graph $K_n$ is at most $n - 1$.
- HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
- handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
- 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$.
- 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 2 vertices (the graph SimpleGraph.completeGraph (Fin 2)) is equal to 1.
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 theorem proves that the glove number of K₂ is 1 by establishing matching upper and lower bounds. The upper bound glove_number(K₂) ≤ 1 follows from the general bound glove_number(K_n) ≤ n - 1 for n = 2. For the lower bound 1 ≤ glove_number(K₂), the proof assumes the infimum is 0 and derives a contradiction using an auxiliary lemma showing that K₂ cannot have a 0-glove clean handshake sequence, because any handshake covering the edge {0, 1} would require an element of the empty type Fin 0.
Assuming for contradiction that K₂ admits a clean handshake sequence with 0 gloves, some handshake in the sequence must cover the edge {0, 1}.
We proceed by contradiction: suppose there exists a clean handshake sequence `seq` with 0 gloves covering all edges of the complete graph on Fin 2. The pair s(0, 1) is an edge of K₂ because 0 ≠ 1. By the coverage property `hcov`, there must be some handshake h in `seq` that covers this edge.
rintro ⟨seq, -, hcov⟩ have hedge : (s(0,1) : Sym2 (Fin 2)) ∈ (SimpleGraph.completeGraph (Fin 2)).edgeSet := by simp [SimpleGraph.edgeSet] obtain ⟨h, -, -⟩ := hcov _ hedge
No such handshake h can exist, proving that K₂ has no clean handshake sequence with 0 gloves.
Whether h is a single handshake or a double handshake, its definition requires a glove label from Fin 0 × Bool. The first component of this label is an element of Fin 0. Since Fin 0 is empty, `Fin.elim0` yields an immediate contradiction in both cases.
uses
Fin.elim0cases h with | single x a y => exact Fin.elim0 a.1 | double x a b y => exact Fin.elim0 a.1
It suffices to show 1 ≤ glove_number(K₂), as the upper bound glove_number(K₂) ≤ 1 holds.
By antisymmetry (`le_antisymm`), showing equality reduces to proving both inequalities. The upper bound glove_number(K₂) ≤ 1 follows directly from `glove_number_complete_graph_upper_bound` with n = 2, which gives an upper bound of 2 - 1 = 1 for complete graphs of size at least 2.
uses
le_antisymm,glove_number_complete_graph_upper_boundapply le_antisymm · exact glove_number_complete_graph_upper_bound 2 (by norm_num)
To prove 1 ≤ glove_number(K₂), it suffices to assume for contradiction that the infimum of clean handshake sequence lengths is 0.
Unfolding the definition of glove_number as the infimum of glove counts admitting clean sequences, the inequality 1 ≤ inf s is equivalent to inf s ≠ 0 by `Nat.one_le_iff_ne_zero`. We assume for contradiction that the infimum equals 0 (`hzero`).
uses
Nat.one_le_iff_ne_zero· unfold glove_number rw [Nat.one_le_iff_ne_zero] intro hzero
The infimum being 0 implies K₂ has a clean sequence with 0 gloves, contradicting the auxiliary lemma.
The set of valid glove counts is non-empty because k = 1 admits a clean sequence by `glove_number_complete_graph_upper_bound_has_clean_seq 1`. Since the set is non-empty, `Nat.sInf_mem` guarantees its infimum belongs to the set. Under the assumption that this infimum is 0, 0 would be a valid glove count for K₂, directly contradicting `glove_number_k2_no_zero_gloves`.
uses
glove_number_complete_graph_upper_bound_has_clean_seq,Nat.sInf_mem,glove_number_k2_no_zero_gloveshave hne : ({k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 2)) k}).Nonempty := ⟨1, glove_number_complete_graph_upper_bound_has_clean_seq 1⟩ have hmem := Nat.sInf_mem hne rw [hzero] at hmem exact glove_number_k2_no_zero_gloves hmem
Fin.elim0- From an element of the empty type Fin 0, any goal can be deduced.
glove_number_k2_no_zero_gloves- The complete graph on 2 vertices does not admit any clean handshake sequence using 0 gloves.
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 on m + 1 vertices has a clean handshake sequence with m gloves.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.one_le_iff_ne_zero- A natural number n is at least 1 if and only if n ≠ 0.
Nat.sInf_mem- Any non-empty set of natural numbers contains its infimum.
- The verification that {0, 1} is an edge of K₂ (line 5) and the numerical check 2 ≤ 2 (line 14) are dispatched automatically by `simp` and `norm_num`.
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_k2_no_zero_gloves : ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 2)) 0 := by rintro ⟨seq, -, hcov⟩ have hedge : (s(0,1) : Sym2 (Fin 2)) ∈ (SimpleGraph.completeGraph (Fin 2)).edgeSet := by simp [SimpleGraph.edgeSet] obtain ⟨h, -, -⟩ := hcov _ hedge cases h with | single x a y => exact Fin.elim0 a.1 | double x a b y => exact Fin.elim0 a.1/-- The glove number of K_2 is 1. -/theorem glove_number_k2 : glove_number (SimpleGraph.completeGraph (Fin 2)) = 1 := by apply le_antisymm · exact glove_number_complete_graph_upper_bound 2 (by norm_num) · unfold glove_number rw [Nat.one_le_iff_ne_zero] intro hzero have hne : ({k : ℕ | has_clean_handshake_seq (SimpleGraph.completeGraph (Fin 2)) k}).Nonempty := ⟨1, glove_number_complete_graph_upper_bound_has_clean_seq 1⟩ have hmem := Nat.sInf_mem hne rw [hzero] at hmem exact glove_number_k2_no_zero_gloves hmem