AFTD Auto-Formalizing Theoretical Domains

glove_number_complete_graph_no_zero_gloves

theoremverified

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

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.

  1. 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.

    line 4

      rintro ⟨seq, -, hcov⟩
  2. 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.

    lines 5–11

    uses SimpleGraph.mem_edgeSet, SimpleGraph.completeGraph, SimpleGraph.top_adj, ne_eq, Fin.mk.inj_iff.mp

      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
  3. 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.

    lines 12–15

    uses Fin.elim0

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it