AFTD Auto-Formalizing Theoretical Domains

glove_number_complete_graph_eq_iff_not_has_seq

theoremverified

For any integer $n \\ge 2$, the glove number of the complete graph $K_n$ is equal to $n - 1$ if and only if no clean handshake sequence using $n - 2$ gloves covers all edges of $K_n$.

Statement

theorem glove_number_complete_graph_eq_iff_not_has_seq (n : ℕ) (hn : 2 ≤ n) :
    glove_number (SimpleGraph.completeGraph (Fin n)) = n - 1 ↔
    ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) (n - 2)
Source
arXiv:2610.17602 -- Clean handshake sequences
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • glove_number_complete_graph_eq_iff_geFor any integer $n \ge 2$, the glove number of the complete graph $K_n$ is equal to $n - 1$ if and only if it is at least $n - 1$.
  • glove_number_complete_graph_le_iffFor $n \ge 2$ and every $k$, the glove number of $K_n$ is at most $k$ if and only if $K_n$ has a clean handshake sequence with $k$ gloves.
  • 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…
  • 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…
Used by 1

Read back from the Lean

For every natural number $n$ such that $2 \le n$, the glove number of the complete graph on vertices $\mathrm{Fin}(n)$ is equal to $n - 1$ if and only if there does not exist a clean handshake sequence for the complete graph on $\mathrm{Fin}(n)$ using $n - 2$ gloves.

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 equivalence is established by rephrasing both sides in terms of inequalities on the glove number of $K_n$. The condition that the glove number equals $n - 1$ is known to be equivalent to it being at least $n - 1$, while having a clean handshake sequence using $n - 2$ gloves is equivalent to the glove number being at most $n - 2$. Finally, linear arithmetic over the natural numbers proves that $g \ge n - 1 \iff \neg(g \le n - 2)$.

  1. The statement is equivalent to: the glove number of $K_n$ is at least $n - 1$ if and only if it is not at most $n - 2$.

    Rewriting the left-hand side with `glove_number_complete_graph_eq_iff_ge` turns the equality $\operatorname{glove\_number}(K_n) = n - 1$ into $\operatorname{glove\_number}(K_n) \ge n - 1$. Rewriting the right-hand side with the converse direction of `glove_number_complete_graph_le_iff` replaces the existence of a clean handshake sequence using $n - 2$ gloves with $\operatorname{glove\_number}(K_n) \le n - 2$.

    lines 5–6

    uses glove_number_complete_graph_eq_iff_ge, glove_number_complete_graph_le_iff

      rw [glove_number_complete_graph_eq_iff_ge n hn,
        ← glove_number_complete_graph_le_iff n hn (n - 2)]
  2. The equivalence holds, completing the proof. automation

    For any natural number $g$ and integer $n \ge 2$, the condition $g \ge n - 1$ is logically equivalent to $\neg (g \le n - 2)$. The `omega` tactic dispatches this linear integer arithmetic goal automatically.

    line 7

      omega
glove_number_complete_graph_eq_iff_ge
For $n \ge 2$, the glove number of the complete graph $K_n$ is equal to $n - 1$ if and only if it is at least $n - 1$.
glove_number_complete_graph_le_iff
For $n \ge 2$ and any $k$, the glove number of $K_n$ is at most $k$ if and only if $K_n$ has a clean handshake sequence using $k$ gloves.

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 any integer n ≥ 2, the glove number of K_n is n - 1 if and only if there is no clean handshake sequence covering K_n using n - 2 gloves. -/theorem glove_number_complete_graph_eq_iff_not_has_seq (n : ℕ) (hn : 2 ≤ n) :    glove_number (SimpleGraph.completeGraph (Fin n)) = n - 1 ↔    ¬ has_clean_handshake_seq (SimpleGraph.completeGraph (Fin n)) (n - 2) := by  rw [glove_number_complete_graph_eq_iff_ge n hn,    ← glove_number_complete_graph_le_iff n hn (n - 2)]  omega
See it in the graphDiscuss this resultChallenge it