AFTD Auto-Formalizing Theoretical Domains

has_clean_handshake_seq_succ

theoremverified

If 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.

Statement

theorem has_clean_handshake_seq_succ {V : Type*} (G : SimpleGraph V) (k : ℕ) :
    has_clean_handshake_seq G k → has_clean_handshake_seq G (k + 1)
Source
step towards glove_number_complete_graph_open_problem
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
  • opp_glove_sideThe opposite side of a glove side $(g, b)$ in $\Gamma \times \mathrm{Bool}$ is $(g, \neg b)$, representing the inside-out orientation of…
  • HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
  • 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…
  • handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
  • handshake_is_cleanA handshake is clean with respect to a contamination map $t : \Gamma \times \mathrm{Bool} \to \mathrm{Set}(V)$ if no player directly…
  • handshake_update_contamThe updated contamination map after a handshake: players add their germs to the glove sides they touch directly, and in a double handshake…
Used by 1
  • has_clean_handshake_seq_monoIf a graph $G$ admits a clean handshake sequence with $k$ gloves and $k \le k'$, then it admits one with $k'$ gloves.

The proof, explained

If a graph admits a clean handshake sequence with k gloves, we can embed the k gloves into k+1 gloves via Fin.castSucc. Since an extra glove remains untouched and the embedding is injective, all contamination updates and clean conditions are preserved, producing a valid clean handshake sequence with k+1 gloves.

  1. pushed contamination definition

    pushed contamination definition

    lines 11–15

    noncomputable def has_clean_handshake_seq_succ_pushContam {V Γ Γ' : Type*} (f : Γ → Γ')
        (t : Γ × Bool → Set V) : Γ' × Bool → Set V := by
      classical
      exact fun s' => if h : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s' then t h.choose else ∅
    
  2. pushContam on image

    pushContam on image

    lines 16–26

    theorem has_clean_handshake_seq_succ_pushContam_apply {V Γ Γ' : Type*} (f : Γ → Γ')
        (hf : Function.Injective f) (t : Γ × Bool → Set V) (a : Γ × Bool) :
        has_clean_handshake_seq_succ_pushContam f t (has_clean_handshake_seq_succ_sideMap f a) = t a := by
      classical
      unfold has_clean_handshake_seq_succ_pushContam
      split_ifs with h
      · congr 1
        have hspec : (f h.choose.1, h.choose.2) = (f a.1, a.2) := by
          simpa only [has_clean_handshake_seq_succ_sideMap] using Exists.choose_spec h
        exact Prod.ext (hf (Prod.mk.inj hspec).1) (Prod.mk.inj hspec).2
      · exact absurd ⟨a, rfl⟩ h
  3. pushContam outside image

    pushContam outside image

    lines 28–35

    theorem has_clean_handshake_seq_succ_pushContam_of_not_mem {V Γ Γ' : Type*} (f : Γ → Γ')
        (t : Γ × Bool → Set V) (s' : Γ' × Bool)
        (hs' : ¬ ∃ a, has_clean_handshake_seq_succ_sideMap f a = s') :
        has_clean_handshake_seq_succ_pushContam f t s' = ∅ := by
      classical
      unfold has_clean_handshake_seq_succ_pushContam
      exact dif_neg hs'
    
  4. pushContam empty

    pushContam empty

    lines 36–44

    theorem has_clean_handshake_seq_succ_pushContam_empty {V Γ Γ' : Type*} (f : Γ → Γ') :
        has_clean_handshake_seq_succ_pushContam (V := V) f (fun _ => ∅) = fun _ => ∅ := by
      classical
      funext s'
      unfold has_clean_handshake_seq_succ_pushContam
      by_cases h : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'
      · rw [dif_pos h]
      · rw [dif_neg h]
    
  5. sideMap inj

    sideMap inj

    lines 49–57

    theorem has_clean_handshake_seq_succ_sideMap_inj {Γ Γ' : Type*} (f : Γ → Γ')
        (hf : Function.Injective f) (x y : Γ × Bool) :
        has_clean_handshake_seq_succ_sideMap f x = has_clean_handshake_seq_succ_sideMap f y ↔ x = y := by
      constructor
      · intro h
        simp only [has_clean_handshake_seq_succ_sideMap, Prod.mk.injEq] at h
        exact Prod.ext (hf h.1) h.2
      · intro h; rw [h]
    
  6. edge preserved

    edge preserved

    lines 58–62

    theorem has_clean_handshake_seq_succ_edge_mapGlove {V Γ Γ' : Type*} (f : Γ → Γ')
        (h : Handshake V Γ) :
        handshake_edge (has_clean_handshake_seq_succ_mapGlove f h) = handshake_edge h := by
      cases h <;> rfl
    
  7. clean mapped

    clean mapped

    lines 63–82

    theorem has_clean_handshake_seq_succ_clean_mapGlove {V Γ Γ' : Type*} (f : Γ → Γ')
        (hf : Function.Injective f) (h : Handshake V Γ) (t : Γ × Bool → Set V) :
        handshake_is_clean h t →
          handshake_is_clean (has_clean_handshake_seq_succ_mapGlove f h)
            (has_clean_handshake_seq_succ_pushContam f t) := by
      intro hc
      cases h with
      | single x a y =>
        simp only [has_clean_handshake_seq_succ_mapGlove, handshake_is_clean] at hc ⊢
        rw [← has_clean_handshake_seq_succ_sideMap_opp,
          has_clean_handshake_seq_succ_pushContam_apply f hf,
          has_clean_handshake_seq_succ_pushContam_apply f hf]
        exact hc
      | double x a b y =>
        simp only [has_clean_handshake_seq_succ_mapGlove, handshake_is_clean] at hc ⊢
        refine ⟨?_, ?_, ?_⟩
        · intro he; exact hc.1 (hf he)
        · rw [has_clean_handshake_seq_succ_pushContam_apply f hf]; exact hc.2.1
        · rw [has_clean_handshake_seq_succ_pushContam_apply f hf]; exact hc.2.2
    
  8. update commutes

    update commutes

    lines 83–129

    theorem has_clean_handshake_seq_succ_pushContam_update {V Γ Γ' : Type*}
        [DecidableEq Γ] [DecidableEq Γ'] (f : Γ → Γ') (hf : Function.Injective f)
        (h : Handshake V Γ) (t : Γ × Bool → Set V) :
        has_clean_handshake_seq_succ_pushContam f (handshake_update_contam h t)
          = handshake_update_contam (has_clean_handshake_seq_succ_mapGlove f h)
              (has_clean_handshake_seq_succ_pushContam f t) := by
      classical
      cases h with
      | single x a y =>
        funext s'
        by_cases hs' : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'
        · obtain ⟨a', ha'⟩ := hs'
          rw [← ha']
          simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam,
            ← has_clean_handshake_seq_succ_sideMap_opp,
            has_clean_handshake_seq_succ_pushContam_apply f hf,
            has_clean_handshake_seq_succ_sideMap_inj f hf]
        · rw [has_clean_handshake_seq_succ_pushContam_of_not_mem f _ s' hs']
          have h1 : s' ≠ has_clean_handshake_seq_succ_sideMap f a := fun he => hs' ⟨a, he.symm⟩
          have h2 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f a) := by
            rw [← has_clean_handshake_seq_succ_sideMap_opp]
            exact fun he => hs' ⟨opp_glove_side a, he.symm⟩
          simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam, h1, h2,
            has_clean_handshake_seq_succ_pushContam_of_not_mem f t s' hs']
          simp
      | double x a b y =>
        funext s'
        by_cases hs' : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'
        · obtain ⟨a', ha'⟩ := hs'
          rw [← ha']
          simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam,
            ← has_clean_handshake_seq_succ_sideMap_opp,
            has_clean_handshake_seq_succ_pushContam_apply f hf,
            has_clean_handshake_seq_succ_sideMap_inj f hf]
        · rw [has_clean_handshake_seq_succ_pushContam_of_not_mem f _ s' hs']
          have h1 : s' ≠ has_clean_handshake_seq_succ_sideMap f a := fun he => hs' ⟨a, he.symm⟩
          have h2 : s' ≠ has_clean_handshake_seq_succ_sideMap f b := fun he => hs' ⟨b, he.symm⟩
          have h3 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f a) := by
            rw [← has_clean_handshake_seq_succ_sideMap_opp]
            exact fun he => hs' ⟨opp_glove_side a, he.symm⟩
          have h4 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f b) := by
            rw [← has_clean_handshake_seq_succ_sideMap_opp]
            exact fun he => hs' ⟨opp_glove_side b, he.symm⟩
          simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam, h1, h2, h3, h4,
            has_clean_handshake_seq_succ_pushContam_of_not_mem f t s' hs']
          simp
    
  9. seq mapped

    seq mapped

    lines 130–147

    theorem has_clean_handshake_seq_succ_clean_seq_map {V Γ Γ' : Type*}
        [DecidableEq Γ] [DecidableEq Γ'] (f : Γ → Γ') (hf : Function.Injective f) :
        ∀ (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V),
          CleanHandshakeSeq seq t →
          CleanHandshakeSeq (seq.map (has_clean_handshake_seq_succ_mapGlove f))
            (has_clean_handshake_seq_succ_pushContam f t) := by
      intro seq t hseq
      induction hseq with
      | nil t => exact CleanHandshakeSeq.nil _
      | cons h seq t hclean htail ih =>
        rw [List.map_cons]
        refine CleanHandshakeSeq.cons (has_clean_handshake_seq_succ_mapGlove f h)
          (seq.map (has_clean_handshake_seq_succ_mapGlove f))
          (has_clean_handshake_seq_succ_pushContam f t) ?_ ?_
        · exact has_clean_handshake_seq_succ_clean_mapGlove f hf h t hclean
        · rw [← has_clean_handshake_seq_succ_pushContam_update f hf h t]
          exact ih
    
  10. main theorem

    main theorem

    lines 149–161

    theorem has_clean_handshake_seq_succ {V : Type*} (G : SimpleGraph V) (k : ℕ) :
        has_clean_handshake_seq G k → has_clean_handshake_seq G (k + 1) := by
      rintro ⟨seq, hclean, hcover⟩
      refine ⟨seq.map (has_clean_handshake_seq_succ_mapGlove (Fin.castSucc (n := k))), ?_, ?_⟩
      · have h := has_clean_handshake_seq_succ_clean_seq_map (f := Fin.castSucc (n := k))
            (Fin.castSucc_injective k) seq (fun _ => ∅) hclean
        rw [has_clean_handshake_seq_succ_pushContam_empty] at h
        exact h
      · intro e he
        obtain ⟨h, hh, hedge⟩ := hcover e he
        refine ⟨has_clean_handshake_seq_succ_mapGlove (Fin.castSucc (n := k)) h, ?_, ?_⟩
        · simp only [List.mem_map]; exact ⟨h, hh, rfl⟩
        · rw [has_clean_handshake_seq_succ_edge_mapGlove]; exact hedge

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

def has_clean_handshake_seq_succ_sideMap {Γ Γ' : Type*} (f : Γ → Γ') :    Γ × Bool → Γ' × Bool := fun s => (f s.1, s.2)def has_clean_handshake_seq_succ_mapGlove {V Γ Γ' : Type*} (f : Γ → Γ') :    Handshake V Γ → Handshake V Γ'  | Handshake.single x a y => Handshake.single x (has_clean_handshake_seq_succ_sideMap f a) y  | Handshake.double x a b y =>      Handshake.double x (has_clean_handshake_seq_succ_sideMap f a)        (has_clean_handshake_seq_succ_sideMap f b) ynoncomputable def has_clean_handshake_seq_succ_pushContam {V Γ Γ' : Type*} (f : Γ → Γ')    (t : Γ × Bool → Set V) : Γ' × Bool → Set V := by  classical  exact fun s' => if h : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s' then t h.choose else ∅theorem has_clean_handshake_seq_succ_pushContam_apply {V Γ Γ' : Type*} (f : Γ → Γ')    (hf : Function.Injective f) (t : Γ × Bool → Set V) (a : Γ × Bool) :    has_clean_handshake_seq_succ_pushContam f t (has_clean_handshake_seq_succ_sideMap f a) = t a := by  classical  unfold has_clean_handshake_seq_succ_pushContam  split_ifs with h  · congr 1    have hspec : (f h.choose.1, h.choose.2) = (f a.1, a.2) := by      simpa only [has_clean_handshake_seq_succ_sideMap] using Exists.choose_spec h    exact Prod.ext (hf (Prod.mk.inj hspec).1) (Prod.mk.inj hspec).2  · exact absurd ⟨a, rfl⟩ htheorem has_clean_handshake_seq_succ_pushContam_of_not_mem {V Γ Γ' : Type*} (f : Γ → Γ')    (t : Γ × Bool → Set V) (s' : Γ' × Bool)    (hs' : ¬ ∃ a, has_clean_handshake_seq_succ_sideMap f a = s') :    has_clean_handshake_seq_succ_pushContam f t s' = ∅ := by  classical  unfold has_clean_handshake_seq_succ_pushContam  exact dif_neg hs'theorem has_clean_handshake_seq_succ_pushContam_empty {V Γ Γ' : Type*} (f : Γ → Γ') :    has_clean_handshake_seq_succ_pushContam (V := V) f (fun _ => ∅) = fun _ => ∅ := by  classical  funext s'  unfold has_clean_handshake_seq_succ_pushContam  by_cases h : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'  · rw [dif_pos h]  · rw [dif_neg h]theorem has_clean_handshake_seq_succ_sideMap_opp {Γ Γ' : Type*} (f : Γ → Γ') (a : Γ × Bool) :    has_clean_handshake_seq_succ_sideMap f (opp_glove_side a)      = opp_glove_side (has_clean_handshake_seq_succ_sideMap f a) := rfltheorem has_clean_handshake_seq_succ_sideMap_inj {Γ Γ' : Type*} (f : Γ → Γ')    (hf : Function.Injective f) (x y : Γ × Bool) :    has_clean_handshake_seq_succ_sideMap f x = has_clean_handshake_seq_succ_sideMap f y ↔ x = y := by  constructor  · intro h    simp only [has_clean_handshake_seq_succ_sideMap, Prod.mk.injEq] at h    exact Prod.ext (hf h.1) h.2  · intro h; rw [h]theorem has_clean_handshake_seq_succ_edge_mapGlove {V Γ Γ' : Type*} (f : Γ → Γ')    (h : Handshake V Γ) :    handshake_edge (has_clean_handshake_seq_succ_mapGlove f h) = handshake_edge h := by  cases h <;> rfltheorem has_clean_handshake_seq_succ_clean_mapGlove {V Γ Γ' : Type*} (f : Γ → Γ')    (hf : Function.Injective f) (h : Handshake V Γ) (t : Γ × Bool → Set V) :    handshake_is_clean h t →      handshake_is_clean (has_clean_handshake_seq_succ_mapGlove f h)        (has_clean_handshake_seq_succ_pushContam f t) := by  intro hc  cases h with  | single x a y =>    simp only [has_clean_handshake_seq_succ_mapGlove, handshake_is_clean] at hc ⊢    rw [← has_clean_handshake_seq_succ_sideMap_opp,      has_clean_handshake_seq_succ_pushContam_apply f hf,      has_clean_handshake_seq_succ_pushContam_apply f hf]    exact hc  | double x a b y =>    simp only [has_clean_handshake_seq_succ_mapGlove, handshake_is_clean] at hc ⊢    refine ⟨?_, ?_, ?_⟩    · intro he; exact hc.1 (hf he)    · rw [has_clean_handshake_seq_succ_pushContam_apply f hf]; exact hc.2.1    · rw [has_clean_handshake_seq_succ_pushContam_apply f hf]; exact hc.2.2theorem has_clean_handshake_seq_succ_pushContam_update {V Γ Γ' : Type*}    [DecidableEq Γ] [DecidableEq Γ'] (f : Γ → Γ') (hf : Function.Injective f)    (h : Handshake V Γ) (t : Γ × Bool → Set V) :    has_clean_handshake_seq_succ_pushContam f (handshake_update_contam h t)      = handshake_update_contam (has_clean_handshake_seq_succ_mapGlove f h)          (has_clean_handshake_seq_succ_pushContam f t) := by  classical  cases h with  | single x a y =>    funext s'    by_cases hs' : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'    · obtain ⟨a', ha'⟩ := hs'      rw [← ha']      simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam,        ← has_clean_handshake_seq_succ_sideMap_opp,        has_clean_handshake_seq_succ_pushContam_apply f hf,        has_clean_handshake_seq_succ_sideMap_inj f hf]    · rw [has_clean_handshake_seq_succ_pushContam_of_not_mem f _ s' hs']      have h1 : s' ≠ has_clean_handshake_seq_succ_sideMap f a := fun he => hs' ⟨a, he.symm⟩      have h2 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f a) := by        rw [← has_clean_handshake_seq_succ_sideMap_opp]        exact fun he => hs' ⟨opp_glove_side a, he.symm⟩      simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam, h1, h2,        has_clean_handshake_seq_succ_pushContam_of_not_mem f t s' hs']      simp  | double x a b y =>    funext s'    by_cases hs' : ∃ a, has_clean_handshake_seq_succ_sideMap f a = s'    · obtain ⟨a', ha'⟩ := hs'      rw [← ha']      simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam,        ← has_clean_handshake_seq_succ_sideMap_opp,        has_clean_handshake_seq_succ_pushContam_apply f hf,        has_clean_handshake_seq_succ_sideMap_inj f hf]    · rw [has_clean_handshake_seq_succ_pushContam_of_not_mem f _ s' hs']      have h1 : s' ≠ has_clean_handshake_seq_succ_sideMap f a := fun he => hs' ⟨a, he.symm⟩      have h2 : s' ≠ has_clean_handshake_seq_succ_sideMap f b := fun he => hs' ⟨b, he.symm⟩      have h3 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f a) := by        rw [← has_clean_handshake_seq_succ_sideMap_opp]        exact fun he => hs' ⟨opp_glove_side a, he.symm⟩      have h4 : s' ≠ opp_glove_side (has_clean_handshake_seq_succ_sideMap f b) := by        rw [← has_clean_handshake_seq_succ_sideMap_opp]        exact fun he => hs' ⟨opp_glove_side b, he.symm⟩      simp only [has_clean_handshake_seq_succ_mapGlove, handshake_update_contam, h1, h2, h3, h4,        has_clean_handshake_seq_succ_pushContam_of_not_mem f t s' hs']      simptheorem has_clean_handshake_seq_succ_clean_seq_map {V Γ Γ' : Type*}    [DecidableEq Γ] [DecidableEq Γ'] (f : Γ → Γ') (hf : Function.Injective f) :    ∀ (seq : List (Handshake V Γ)) (t : Γ × Bool → Set V),      CleanHandshakeSeq seq t →      CleanHandshakeSeq (seq.map (has_clean_handshake_seq_succ_mapGlove f))        (has_clean_handshake_seq_succ_pushContam f t) := by  intro seq t hseq  induction hseq with  | nil t => exact CleanHandshakeSeq.nil _  | cons h seq t hclean htail ih =>    rw [List.map_cons]    refine CleanHandshakeSeq.cons (has_clean_handshake_seq_succ_mapGlove f h)      (seq.map (has_clean_handshake_seq_succ_mapGlove f))      (has_clean_handshake_seq_succ_pushContam f t) ?_ ?_    · exact has_clean_handshake_seq_succ_clean_mapGlove f hf h t hclean    · rw [← has_clean_handshake_seq_succ_pushContam_update f hf h t]      exact ih/-- An unused glove can always be added: `k` gloves suffice implies `k+1` gloves suffice. -/theorem has_clean_handshake_seq_succ {V : Type*} (G : SimpleGraph V) (k : ℕ) :    has_clean_handshake_seq G k → has_clean_handshake_seq G (k + 1) := by  rintro ⟨seq, hclean, hcover⟩  refine ⟨seq.map (has_clean_handshake_seq_succ_mapGlove (Fin.castSucc (n := k))), ?_, ?_⟩  · have h := has_clean_handshake_seq_succ_clean_seq_map (f := Fin.castSucc (n := k))        (Fin.castSucc_injective k) seq (fun _ => ∅) hclean    rw [has_clean_handshake_seq_succ_pushContam_empty] at h    exact h  · intro e he    obtain ⟨h, hh, hedge⟩ := hcover e he    refine ⟨has_clean_handshake_seq_succ_mapGlove (Fin.castSucc (n := k)) h, ?_, ?_⟩    · simp only [List.mem_map]; exact ⟨h, hh, rfl⟩    · rw [has_clean_handshake_seq_succ_edge_mapGlove]; exact hedge
See it in the graphDiscuss this resultChallenge it