glove_number_complete_graph_eq_iff_ge
For 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$.
Statement
theorem glove_number_complete_graph_eq_iff_ge (n : ℕ) (hn : 2 ≤ n) :
glove_number (SimpleGraph.completeGraph (Fin n)) = n - 1 ↔
n - 1 ≤ glove_number (SimpleGraph.completeGraph (Fin n))- Source
- arXiv:2610.17602 Theorem 3 (Clean handshake sequences)
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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$.
- Used by 1
- glove_number_complete_graph_eq_iff_not_has_seqFor 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…
Read back from the Lean
For every natural number $n$ such that $2 \le n$, the glove number of the complete graph on the vertex set $\mathrm{Fin}(n)$ is equal to $n - 1$ if and only if $n - 1 \le \mathrm{glove\_number}(\mathrm{completeGraph}(\mathrm{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 establishes that the glove number of K_n equals n - 1 if and only if it is at least n - 1 by using the known upper bound that the glove number is at most n - 1. The forward implication is trivial by reflexivity of ≤, while the reverse implication combines the hypothesis with the upper bound and applies antisymmetry.
The glove number of K_n is at most n - 1.
By the lemma `glove_number_complete_graph_upper_bound`, the glove number of the complete graph on n vertices is bounded from above by n - 1 when n ≥ 2.
uses
glove_number_complete_graph_upper_boundhave h := glove_number_complete_graph_upper_bound n hnIf the glove number of K_n is equal to n - 1, then it is at least n - 1.
We split the "if and only if" into both directions. In the forward direction, assuming the glove number equals n - 1, substituting this equality into the desired inequality n - 1 ≤ glove_number(K_n) yields n - 1 ≤ n - 1, which holds by reflexivity.
constructor · intro heq rw [heq]
If the glove number of K_n is at least n - 1, then it is equal to n - 1.
In the reverse direction, assuming n - 1 ≤ glove_number(K_n) and combining it with the upper bound glove_number(K_n) ≤ n - 1, the antisymmetry of ≤ (`le_antisymm`) proves the equality.
uses
le_antisymm· intro hle exact le_antisymm h hle
glove_number_complete_graph_upper_bound- For any n ≥ 2, the glove number of the complete graph K_n is at most n - 1.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
- In line 8, rewriting with the hypothesis `heq` replaces the glove number with `n - 1`, resulting in `n - 1 ≤ n - 1`, which Lean's `rw` tactic closes automatically by reflexivity.
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, the glove number of K_n is equal to n - 1 if and only if it is at least n - 1. -/theorem glove_number_complete_graph_eq_iff_ge (n : ℕ) (hn : 2 ≤ n) : glove_number (SimpleGraph.completeGraph (Fin n)) = n - 1 ↔ n - 1 ≤ glove_number (SimpleGraph.completeGraph (Fin n)) := by have h := glove_number_complete_graph_upper_bound n hn constructor · intro heq rw [heq] · intro hle exact le_antisymm h hle