has_clean_handshake_seq_mono
If a graph $G$ admits a clean handshake sequence with $k$ gloves and $k \le k'$, then it admits one with $k'$ gloves.
Statement
theorem has_clean_handshake_seq_mono {V : Type*} (G : SimpleGraph V) {k k' : ℕ} (hkk : k ≤ k') (h : has_clean_handshake_seq G k) : has_clean_handshake_seq G k'
- Source
- step towards glove_number_complete_graph_open_problem
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- has_clean_handshake_seq_succIf a graph $G$ admits a clean handshake sequence with $k$ gloves, then it admits one with $k+1$ gloves: an extra glove can be left unused.
- 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…
- Used by 1
- glove_number_le_iff_has_clean_handshake_seqIf some number of gloves suffices for a graph $G$, then for every $k$ the glove number of $G$ is at most $k$ if and only if $G$ has a…
The proof, explained
The proof proceeds by induction on the inequality $k \le k'$. The base case $k' = k$ is given directly by the hypothesis. For the inductive step, the lemma `has_clean_handshake_seq_succ` increases the available glove count by one.
The claim holds in the base case $k' = k$.
We induct on the inequality $k \le k'$. In the base case (`refl`), $k' = k$, and the goal is to show that $G$ has a clean handshake sequence with $k$ gloves, which is directly given by the assumption $h$.
induction hkk with | refl => exact h
If the claim holds for $m$, it also holds for $m + 1$.
In the inductive step (`step`), we assume by the induction hypothesis `ih` that $G$ has a clean handshake sequence with $m$ gloves. Applying `has_clean_handshake_seq_succ` to `ih` shows that $G$ also admits a clean handshake sequence with $m + 1$ gloves.
uses
has_clean_handshake_seq_succ| step hkk ih => exact has_clean_handshake_seq_succ G _ ih
has_clean_handshake_seq_succ- If a graph admits a clean handshake sequence with $k$ gloves, it also admits one with $k + 1$ 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.
/-- Glove counts admitting a covering sequence form an upward closed set. -/theorem has_clean_handshake_seq_mono {V : Type*} (G : SimpleGraph V) {k k' : ℕ} (hkk : k ≤ k') (h : has_clean_handshake_seq G k) : has_clean_handshake_seq G k' := by induction hkk with | refl => exact h | step hkk ih => exact has_clean_handshake_seq_succ G _ ih