glove_number_complete_graph_no_zero_gloves
For any integer $n \ge 2$, there is no clean handshake sequence with zero gloves covering all edges of the complete graph $K_n$.
Statement
theorem glove_number_complete_graph_no_zero_gloves (n : ℕ) (hn : 2 ≤ n) :
¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) 0- Source
- arXiv:2610.17602 Section 2 (Clean handshake sequences)
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
- HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
- Used by 1
- glove_number_complete_graph_posFor every integer $n \ge 2$, the glove number of the complete graph $K_n$ is at least 1.
Read back from the Lean
For every natural number $n$ such that $2 \le n$, there does not exist a clean handshake sequence using 0 gloves (Fin 0) that covers all edges of the complete graph on vertices Fin 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
The proof proceeds by contradiction. If a clean handshake sequence using zero gloves could cover the complete graph K_n for n ≥ 2, it would in particular have to cover the edge between vertices 0 and 1. However, every handshake constructor (single or double) requires at least one glove from the glove set Fin 0, which is empty, so no such handshake can exist.
Assume for contradiction that there exists a clean handshake sequence with zero gloves covering all edges of K_n.
We assume the negation of the theorem and unpack the existential hypothesis into a handshake sequence seq, its cleanliness condition (which is unused), and a coverage hypothesis hcov asserting that every edge in the complete graph K_n is covered by some handshake in seq.
rintro ⟨seq, -, hcov⟩
The unordered pair {0, 1} is an edge in the complete graph K_n.
Because n ≥ 2, the elements 0 and 1 are well-defined vertices in Fin n (justified by linear arithmetic). By definition, an unordered pair forms an edge of K_n if and only if the vertices are adjacent, which in a complete graph means they are distinct. Assuming for contradiction that 0 = 1 in Fin n, their underlying natural numbers would be equal, yielding 0 = 1, which omega refutes.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.completeGraph,SimpleGraph.top_adj,ne_eq,Fin.mk.inj_iff.mphave hedge : s((⟨0, by omega⟩ : Fin n), (⟨1, by omega⟩ : Fin n)) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by rw [SimpleGraph.mem_edgeSet] simp only [SimpleGraph.completeGraph, SimpleGraph.top_adj, ne_eq] intro hne have := Fin.mk.inj_iff.mp hne omega
Contradiction: covering the edge requires a handshake, but any handshake requires at least one glove and no gloves exist.
Applying the covering hypothesis hcov to the edge {0, 1} yields a handshake h in seq that covers it. By the inductive definition of Handshake, h must be either a single-glove handshake or a double-glove handshake. In both cases, the constructor requires a glove identifier a.1 ∈ Fin 0. Since the type Fin 0 has no elements, Fin.elim0 closes both branches with a contradiction.
uses
Fin.elim0obtain ⟨h, hmem, -⟩ := hcov _ hedge cases h with | single x a y => exact Fin.elim0 a.1 | double x a b y => exact Fin.elim0 a.1
Fin.elim0- An element of the empty type Fin 0 is impossible, so it can prove any goal.
Fin.mk.inj_iff.mp- If two elements of Fin n are equal, their underlying natural numbers are equal.
ne_eq- The inequality a ≠ b is definitionally the proposition ¬(a = b).
SimpleGraph.completeGraph- The complete graph on a vertex type V, in which all distinct vertices are adjacent.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
SimpleGraph.top_adj- In the complete graph ⊤, two vertices are adjacent if and only if they are not equal.
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.
/-- For n ≥ 2, there is no clean handshake sequence for K_n using zero gloves. -/theorem glove_number_complete_graph_no_zero_gloves (n : ℕ) (hn : 2 ≤ n) : ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) 0 := by rintro ⟨seq, -, hcov⟩ have hedge : s((⟨0, by omega⟩ : Fin n), (⟨1, by omega⟩ : Fin n)) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by rw [SimpleGraph.mem_edgeSet] simp only [SimpleGraph.completeGraph, SimpleGraph.top_adj, ne_eq] intro hne have := Fin.mk.inj_iff.mp hne omega obtain ⟨h, hmem, -⟩ := hcov _ hedge cases h with | single x a y => exact Fin.elim0 a.1 | double x a b y => exact Fin.elim0 a.1