AFTD Auto-Formalizing Theoretical Domains

glove_number_k2

theoremverifiedformalization

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

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.

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

    lines 3–6

      rintro ⟨seq, -, hcov⟩
      have hedge : (s(0,1) : Sym2 (Fin 2)) ∈ (SimpleGraph.completeGraph (Fin 2)).edgeSet := by
        simp [SimpleGraph.edgeSet]
      obtain ⟨h, -, -⟩ := hcov _ hedge
  2. 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.

    lines 7–9

    uses Fin.elim0

      cases h with
      | single x a y => exact Fin.elim0 a.1
      | double x a b y => exact Fin.elim0 a.1
  3. 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.

    lines 13–14

    uses le_antisymm, glove_number_complete_graph_upper_bound

      apply le_antisymm
      · exact glove_number_complete_graph_upper_bound 2 (by norm_num)
  4. 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`).

    lines 15–17

    uses Nat.one_le_iff_ne_zero

      · unfold glove_number
        rw [Nat.one_le_iff_ne_zero]
        intro hzero
  5. 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`.

    lines 18–22

    uses glove_number_complete_graph_upper_bound_has_clean_seq, Nat.sInf_mem, glove_number_k2_no_zero_gloves

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

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