AFTD Auto-Formalizing Theoretical Domains

has_clean_handshake_seq_mono

theoremverified

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

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.

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

    lines 4–5

      induction hkk with
      | refl => exact h
  2. 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.

    line 6

    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

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