glove_number_complete_graph_eq_iff_not_has_seq
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
- glove_number_complete_graph_eq_of_not_has_seqFor any integer $n \\ge 2$, if no clean handshake sequence using $n - 2$ gloves covers all edges of $K_n$, then the glove number of $K_n$…
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)$.
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$.
uses
glove_number_complete_graph_eq_iff_ge,glove_number_complete_graph_le_iffrw [glove_number_complete_graph_eq_iff_ge n hn, ← glove_number_complete_graph_le_iff n hn (n - 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.
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
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 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