AFTD Auto-Formalizing Theoretical Domains

glove_number_complete_graph_upper_bound

theoremverifiedformalization

For all integers $n \ge 2$, the glove number of the complete graph $K_n$ is at most $n - 1$.

Statement

theorem glove_number_complete_graph_upper_bound (n : ℕ) (hn : 2 ≤ n) : glove_number (SimpleGraph.completeGraph (Fin n)) ≤ n - 1
Formalizes
scout/2610-17602-clean-handshake-sequences.md:653
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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…
  • 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…
  • 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…
  • HandshakeA handshake between vertices in $V$ using gloves from $\Gamma$, which is either single-gloved (one vertex wears a glove side inside, the…
  • CleanHandshakeSeqInductive predicate stating that a sequence of handshakes is clean when executed starting from an initial contamination map $t$.
  • 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…
  • handshake_edgeThe unordered edge in $\mathrm{Sym}^2(V)$ covered by a handshake between vertices $x$ and $y$, namely $s(x, y)$.
  • 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…
Used by 3

Read back from the Lean

For any natural number $n$ such that $2 \le n$, the glove number of the complete graph on $n$ vertices (SimpleGraph.completeGraph (Fin n)) is less than or equal to $n - 1$. Here, the glove number of a simple graph $G$ is defined as the infimum (sInf) in $\mathbb{N}$ of the set of natural numbers $k$ for which $G$ admits a clean handshake sequence using gloves indexed by $\text{Fin } k$. A clean handshake sequence is a list of handshakes (single or double, involving one or two gloves in $\text{Fin } k \times \text{Bool}$) that satisfies the CleanHandshakeSeq predicate starting with an empty contamination state, and such that every edge in $G$ is covered by at least one handshake in the sequence.

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

To show that the complete graph K_n has glove number at most n - 1 for n ≥ 2, we set m = n - 1 and model the n vertices as m regular vertices plus one special last vertex. We construct an explicit clean handshake sequence using m gloves in two phases: Phase 1 performs double handshakes on the true sides of distinct gloves to cover all edges between regular vertices, while Phase 2 performs single handshakes on the false sides between the last vertex and each regular vertex. An invariant guarantees that false sides remain completely uncontaminated throughout Phase 1, allowing Phase 2 to execute cleanly. Because this sequence covers all edges of K_n using m gloves, the glove number is at most n - 1.

  1. Invariant 1 implies Invariant 2.

    Invariant 1 requires that for each glove k, the false side is empty, which is a subset of {Fin.last m} by Set.empty_subset, and the true side is a subset of {k.castSucc}. This immediately yields both conjuncts of Invariant 2.

    lines 21–25

    uses Set.empty_subset

      intro k
      constructor
      · rw [ht.1 k]
        exact Set.empty_subset _
      · exact ht.2 k
  2. Every Phase 1 handshake is clean under Invariant 1.

    A Phase 1 handshake is a double handshake between distinct vertices i and j using sides (i, true) and (j, true). Cleanliness requires that i ≠ j and that the contamination on the active sides is bounded by {i.castSucc} and {j.castSucc}, which holds directly by Invariant 1.

    lines 32–34

      rcases hh with ⟨i, j, hij, rfl⟩
      dsimp [handshake_is_clean]
      exact ⟨hij, ht.2 i, ht.2 j⟩
  3. A Phase 1 handshake preserves Invariant 1.

    Updating contamination after a Phase 1 double handshake between i and j modifies only the active true sides and the opposite false sides. For any glove k, the false side (k, false) can only receive contamination from t(i, false) ∪ t(j, false), which is ∅ ∪ ∅ = ∅ by Invariant 1, or remains untouched. The true side (k, true) receives at most {k.castSucc} if k = i or k = j, and is otherwise unchanged, preserving Invariant 1.

    lines 41–67

    uses if_neg, Set.union_empty, Set.union_subset, Set.Subset.refl

      rcases hh with ⟨i, j, hij, rfl⟩
      constructor
      · intro k
        change (if (k, false) = (i, true) then t (i, true) ∪ {i.castSucc}
                else if (k, false) = (j, true) then t (j, true) ∪ {j.castSucc}
                else if (k, false) = (i, false) ∨ (k, false) = (j, false) then t (i, false) ∪ t (j, false)
                else t (k, false)) = ∅
        have h1 : ¬ (k, false) = (i, true) := by intro h; cases h
        have h2 : ¬ (k, false) = (j, true) := by intro h; cases h
        rw [if_neg h1, if_neg h2]
        split_ifs with h3
        · rw [ht.1 i, ht.1 j, Set.union_empty]
        · exact ht.1 k
      · intro k
        change (if (k, true) = (i, true) then t (i, true) ∪ {i.castSucc}
                else if (k, true) = (j, true) then t (j, true) ∪ {j.castSucc}
                else if (k, true) = (i, false) ∨ (k, true) = (j, false) then t (i, false) ∪ t (j, false)
                else t (k, true)) ⊆ {k.castSucc}
        split_ifs with h1 h2 h3
        · injection h1 with hi
          subst hi
          exact Set.union_subset (ht.2 k) (Set.Subset.refl _)
        · injection h2 with hj
          subst hj
          exact Set.union_subset (ht.2 k) (Set.Subset.refl _)
        · rcases h3 with h3 | h3 <;> cases h3
        · exact ht.2 k
  4. Every Phase 2 handshake is clean under Invariant 2.

    A Phase 2 handshake is a single handshake between Fin.last m and i.castSucc using side (i, false). Cleanliness requires t(i, false) ⊆ {Fin.last m} and t(i, true) ⊆ {i.castSucc}, which are precisely the two conditions guaranteed by Invariant 2.

    lines 74–76

      rcases hh with ⟨i, rfl⟩
      dsimp [handshake_is_clean, opp_glove_side]
      exact ⟨(ht i).1, (ht i).2⟩
  5. A Phase 2 handshake preserves Invariant 2.

    Updating contamination after a Phase 2 handshake on glove i only adds Fin.last m to (i, false) and i.castSucc to (i, true). By Invariant 2, the existing contaminations are already subsets of these singletons, so the union remains within the singletons. All other gloves remain unchanged, so Invariant 2 is preserved.

    lines 83–103

    uses Set.union_subset, Set.Subset.refl

      rcases hh with ⟨i, rfl⟩
      intro k
      constructor
      · change (if (k, false) = (i, false) then t (i, false) ∪ {Fin.last m}
                else if (k, false) = (i, true) then t (i, true) ∪ {i.castSucc}
                else t (k, false)) ⊆ {Fin.last m}
        split_ifs with h1 h2
        · injection h1 with hi
          subst hi
          exact Set.union_subset (ht k).1 (Set.Subset.refl _)
        · cases h2
        · exact (ht k).1
      · change (if (k, true) = (i, false) then t (i, false) ∪ {Fin.last m}
                else if (k, true) = (i, true) then t (i, true) ∪ {i.castSucc}
                else t (k, true)) ⊆ {k.castSucc}
        split_ifs with h1 h2
        · cases h1
        · injection h2 with hi
          subst hi
          exact Set.union_subset (ht k).2 (Set.Subset.refl _)
        · exact (ht k).2
  6. Any sequence of Phase 2 handshakes is clean starting from an Invariant 2 state.

    By induction on the sequence. The empty sequence is clean by CleanHandshakeSeq.nil. For the induction step, the head handshake is clean by glove_number_complete_graph_upper_bound_phase2_step_clean, the updated state satisfies Invariant 2 by glove_number_complete_graph_upper_bound_phase2_step_inv, and the tail is clean by the induction hypothesis, so CleanHandshakeSeq.cons finishes the step.

    lines 110–118

    uses CleanHandshakeSeq.nil, List.mem_cons_self, List.mem_cons_of_mem, glove_number_complete_graph_upper_bound_phase2_step_clean, glove_number_complete_graph_upper_bound_phase2_step_inv, CleanHandshakeSeq.cons

      induction seq generalizing t with
      | nil => exact CleanHandshakeSeq.nil t
      | cons h rest ih =>
        have hh : glove_number_complete_graph_upper_bound_is_phase2_handshake h := hseq h List.mem_cons_self
        have hrest : ∀ h' ∈ rest, glove_number_complete_graph_upper_bound_is_phase2_handshake h' :=
          fun h' mh' => hseq h' (List.mem_cons_of_mem _ mh')
        have hc := glove_number_complete_graph_upper_bound_phase2_step_clean hh ht
        have hi := glove_number_complete_graph_upper_bound_phase2_step_inv hh ht
        exact CleanHandshakeSeq.cons h rest t hc (ih hrest hi)
  7. The concatenation of a Phase 1 sequence and a Phase 2 sequence is clean starting from an Invariant 1 state.

    By induction on the Phase 1 sequence. In the base case, the Phase 1 sequence is empty; since Invariant 1 implies Invariant 2, the Phase 2 sequence is clean by glove_number_complete_graph_upper_bound_clean_seq_phase2. In the inductive step, the head handshake is clean and preserves Invariant 1, and the induction hypothesis applies to the rest.

    lines 126–136

    uses glove_number_complete_graph_upper_bound_clean_seq_phase2, glove_number_complete_graph_upper_bound_inv1_imp_inv2, List.mem_cons_self, List.mem_cons_of_mem, glove_number_complete_graph_upper_bound_phase1_step_clean, glove_number_complete_graph_upper_bound_phase1_step_inv, CleanHandshakeSeq.cons

      induction seq1 generalizing t with
      | nil =>
        exact glove_number_complete_graph_upper_bound_clean_seq_phase2 seq2 hseq2
          (glove_number_complete_graph_upper_bound_inv1_imp_inv2 ht)
      | cons h rest ih =>
        have hh : glove_number_complete_graph_upper_bound_is_phase1_handshake h := hseq1 h List.mem_cons_self
        have hrest : ∀ h' ∈ rest, glove_number_complete_graph_upper_bound_is_phase1_handshake h' :=
          fun h' mh' => hseq1 h' (List.mem_cons_of_mem _ mh')
        have hc := glove_number_complete_graph_upper_bound_phase1_step_clean hh ht
        have hi := glove_number_complete_graph_upper_bound_phase1_step_inv hh ht
        exact CleanHandshakeSeq.cons h (rest ++ seq2) t hc (ih hrest hi)
  8. All handshakes in phase1 m satisfy the Phase 1 handshake definition.

    Unfolding phase1 m, the elements are generated by flat-mapping and filter-mapping over pairs i, j in List.finRange m with the condition i ≠ j, so each element is a double handshake between distinct indices.

    lines 154–163

    uses List.mem_flatMap, List.mem_filterMap

      intro h hh
      dsimp [glove_number_complete_graph_upper_bound_phase1] at hh
      rw [List.mem_flatMap] at hh
      rcases hh with ⟨i, _, hi⟩
      rw [List.mem_filterMap] at hi
      rcases hi with ⟨j, _, hj⟩
      split_ifs at hj with hij
      · injection hj with heq
        subst heq
        exact ⟨i, j, hij, rfl⟩
  9. All handshakes in phase2 m satisfy the Phase 2 handshake definition.

    Unfolding phase2 m, the elements are obtained by mapping over List.finRange m, each producing a single handshake between Fin.last m and i.castSucc using side (i, false).

    lines 168–172

    uses List.mem_map

      intro h hh
      dsimp [glove_number_complete_graph_upper_bound_phase2] at hh
      rw [List.mem_map] at hh
      rcases hh with ⟨i, _, rfl⟩
      exact ⟨i, rfl⟩
  10. For distinct indices i and j, the double handshake between them belongs to phase1 m.

    Both i and j belong to List.finRange m, and because i ≠ j, the filterMap condition succeeds, placing the double handshake in the list.

    lines 177–182

    uses List.mem_flatMap, List.mem_finRange, List.mem_filterMap

      dsimp [glove_number_complete_graph_upper_bound_phase1]
      rw [List.mem_flatMap]
      refine ⟨i, List.mem_finRange i, ?_⟩
      rw [List.mem_filterMap]
      refine ⟨j, List.mem_finRange j, ?_⟩
      simp [hij]
  11. For any index i, the single handshake between Fin.last m and i.castSucc belongs to phase2 m.

    Because i belongs to List.finRange m, mapping the single handshake constructor over the range produces the desired handshake in phase2 m.

    lines 187–189

    uses List.mem_map, List.mem_finRange

      dsimp [glove_number_complete_graph_upper_bound_phase2]
      rw [List.mem_map]
      exact ⟨i, List.mem_finRange i, rfl⟩
  12. Every edge of the complete graph K_{m+1} is covered by phase1 m ++ phase2 m.

    An edge in K_{m+1} is an unordered pair s(u, v) with u ≠ v. By Fin.eq_castSucc_or_eq_last, each vertex is either of the form castSucc or Fin.last m. If both are of the form castSucc, they correspond to distinct indices i ≠ j, so the edge is covered by a Phase 1 double handshake. If one is castSucc and the other is Fin.last m, it is covered by a Phase 2 single handshake. Both cannot be Fin.last m because u ≠ v.

    lines 195–210

    uses Sym2.inductionOn, Fin.eq_castSucc_or_eq_last, List.mem_append_left, glove_number_complete_graph_upper_bound_mem_phase1, List.mem_append_right, glove_number_complete_graph_upper_bound_mem_phase2, Sym2.eq_swap

      induction e using Sym2.inductionOn with
      | hf u v =>
        have huv : u ≠ v := he
        rcases Fin.eq_castSucc_or_eq_last u with (⟨i, rfl⟩ | rfl)
        · rcases Fin.eq_castSucc_or_eq_last v with (⟨j, rfl⟩ | rfl)
          · have hij : i ≠ j := by
              intro h; apply huv; subst h; rfl
            refine ⟨Handshake.double i.castSucc (i, true) (j, true) j.castSucc, ?_, rfl⟩
            exact List.mem_append_left _ (glove_number_complete_graph_upper_bound_mem_phase1 hij)
          · refine ⟨Handshake.single (Fin.last m) (i, false) i.castSucc, ?_, ?_⟩
            · exact List.mem_append_right _ (glove_number_complete_graph_upper_bound_mem_phase2 i)
            · dsimp [handshake_edge]; rw [Sym2.eq_swap]
        · rcases Fin.eq_castSucc_or_eq_last v with (⟨j, rfl⟩ | rfl)
          · refine ⟨Handshake.single (Fin.last m) (j, false) j.castSucc, ?_, rfl⟩
            exact List.mem_append_right _ (glove_number_complete_graph_upper_bound_mem_phase2 j)
          · contradiction
  13. The complete graph K_{m+1} has a clean handshake sequence using m gloves.

    We choose the sequence phase1 m ++ phase2 m. The completely uncontaminated initial state satisfies Invariant 1. By glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2, the sequence is clean from this state, and by glove_number_complete_graph_upper_bound_edges_covered, it covers every edge of the complete graph.

    lines 214–229

    uses Set.empty_subset, glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2, glove_number_complete_graph_upper_bound_phase1_all_is_phase1, glove_number_complete_graph_upper_bound_phase2_all_is_phase2, glove_number_complete_graph_upper_bound_edges_covered

      use glove_number_complete_graph_upper_bound_phase1 m ++
          glove_number_complete_graph_upper_bound_phase2 m
      constructor
      · have hinit : glove_number_complete_graph_upper_bound_inv1
            (fun (_ : Fin m × Bool) => (∅ : Set (Fin (m + 1)))) := by
          constructor
          · intro k; rfl
          · intro k; exact Set.empty_subset _
        exact glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2
          (glove_number_complete_graph_upper_bound_phase1 m)
          (glove_number_complete_graph_upper_bound_phase2 m)
          (glove_number_complete_graph_upper_bound_phase1_all_is_phase1 m)
          (glove_number_complete_graph_upper_bound_phase2_all_is_phase2 m)
          hinit
      · intro e he
        exact glove_number_complete_graph_upper_bound_edges_covered m e he
  14. For any n ≥ 2, the glove number of the complete graph K_n is at most n - 1.

    Since n ≥ 2, we can write n = m + 1 with m = n - 1. The complete graph K_{m+1} admits a clean handshake sequence using m gloves by glove_number_complete_graph_upper_bound_has_clean_seq. Since the glove number is defined as the infimum of the set of valid glove counts, Nat.sInf_le implies that gl(K_n) ≤ m = n - 1.

    lines 233–237

    uses Nat.exists_eq_succ_of_ne_zero, Nat.add_sub_cancel, glove_number_complete_graph_upper_bound_has_clean_seq, Nat.sInf_le

      obtain ⟨m, hm⟩ : ∃ m, n = m + 1 := Nat.exists_eq_succ_of_ne_zero (by omega)
      subst hm
      simp only [Nat.add_sub_cancel]
      have hseq := glove_number_complete_graph_upper_bound_has_clean_seq m
      exact Nat.sInf_le hseq
Set.empty_subset
The empty set is a subset of any set.
if_neg
If a condition c is false, then if c then t else e evaluates to e.
Set.union_empty
The union of any set with the empty set is the set itself.
Set.union_subset
If A ⊆ C and B ⊆ C, then A ∪ B ⊆ C.
Set.Subset.refl
Every set is a subset of itself.
CleanHandshakeSeq.nil
The empty sequence of handshakes is clean for any initial contamination state.
List.mem_cons_self
An element is a member of any list with that element as its head.
List.mem_cons_of_mem
If an element belongs to a list, it also belongs to the list with any element prepended.
glove_number_complete_graph_upper_bound_phase2_step_clean
Any Phase 2 handshake is clean under Invariant 2.
glove_number_complete_graph_upper_bound_phase2_step_inv
Executing a Phase 2 handshake preserves Invariant 2.
CleanHandshakeSeq.cons
Prepending a clean handshake to a clean sequence yields a clean sequence.
glove_number_complete_graph_upper_bound_clean_seq_phase2
Any sequence consisting entirely of Phase 2 handshakes is clean starting from an Invariant 2 state.
glove_number_complete_graph_upper_bound_inv1_imp_inv2
Invariant 1 implies Invariant 2.
glove_number_complete_graph_upper_bound_phase1_step_clean
Any Phase 1 handshake is clean under Invariant 1.
glove_number_complete_graph_upper_bound_phase1_step_inv
Executing a Phase 1 handshake preserves Invariant 1.
List.mem_flatMap
An element belongs to flatMap f l iff it belongs to f a for some a in l.
List.mem_filterMap
An element b belongs to filterMap f l iff f a = some b for some a in l.
List.mem_map
An element b belongs to map f l iff b = f a for some a in l.
List.mem_finRange
Every element of Fin n belongs to List.finRange n.
Sym2.inductionOn
Every unordered pair in Sym2 is of the form s(x, y) for some vertices x and y.
Fin.eq_castSucc_or_eq_last
Every element of Fin (n + 1) is either j.castSucc for some j in Fin n or is the last element Fin.last n.
List.mem_append_left
If an element belongs to the first list, it belongs to the concatenated list.
glove_number_complete_graph_upper_bound_mem_phase1
For any distinct i and j in Fin m, the Phase 1 double handshake between i and j belongs to phase1 m.
List.mem_append_right
If an element belongs to the second list, it belongs to the concatenated list.
glove_number_complete_graph_upper_bound_mem_phase2
For any i in Fin m, the Phase 2 single handshake for i belongs to phase2 m.
Sym2.eq_swap
Unordered pairs are symmetric: s(a, b) = s(b, a).
glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2
The concatenation of a Phase 1 sequence and a Phase 2 sequence is clean starting from an Invariant 1 state.
glove_number_complete_graph_upper_bound_phase1_all_is_phase1
Every handshake generated in phase1 m is a valid Phase 1 handshake.
glove_number_complete_graph_upper_bound_phase2_all_is_phase2
Every handshake generated in phase2 m is a valid Phase 2 handshake.
glove_number_complete_graph_upper_bound_edges_covered
Every edge of the complete graph K_{m+1} is realized by some handshake in phase1 m ++ phase2 m.
Nat.exists_eq_succ_of_ne_zero
Any non-zero natural number is a successor.
Nat.add_sub_cancel
For any natural numbers, (n + m) - m = n.
glove_number_complete_graph_upper_bound_has_clean_seq
The complete graph K_{m+1} has a clean handshake sequence using m gloves.
Nat.sInf_le
If m belongs to a set of natural numbers, the infimum of that set is at most m.

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 glove_number_complete_graph_upper_bound_is_phase1_handshake {m : ℕ}    (h : Handshake (Fin (m + 1)) (Fin m)) : Prop :=  ∃ (i j : Fin m), i ≠ j ∧ h = Handshake.double i.castSucc (i, true) (j, true) j.castSuccdef glove_number_complete_graph_upper_bound_is_phase2_handshake {m : ℕ}    (h : Handshake (Fin (m + 1)) (Fin m)) : Prop :=  ∃ (i : Fin m), h = Handshake.single (Fin.last m) (i, false) i.castSuccdef glove_number_complete_graph_upper_bound_inv1 {m : ℕ}    (t : Fin m × Bool → Set (Fin (m + 1))) : Prop :=  (∀ k, t (k, false) = ∅) ∧ (∀ k, t (k, true) ⊆ {k.castSucc})def glove_number_complete_graph_upper_bound_inv2 {m : ℕ}    (t : Fin m × Bool → Set (Fin (m + 1))) : Prop :=  ∀ k, t (k, false) ⊆ {Fin.last m} ∧ t (k, true) ⊆ {k.castSucc}lemma glove_number_complete_graph_upper_bound_inv1_imp_inv2 {m : ℕ}    {t : Fin m × Bool → Set (Fin (m + 1))}    (ht : glove_number_complete_graph_upper_bound_inv1 t) :    glove_number_complete_graph_upper_bound_inv2 t := by  intro k  constructor  · rw [ht.1 k]    exact Set.empty_subset _  · exact ht.2 klemma glove_number_complete_graph_upper_bound_phase1_step_clean {m : ℕ}    {h : Handshake (Fin (m + 1)) (Fin m)} {t : Fin m × Bool → Set (Fin (m + 1))}    (hh : glove_number_complete_graph_upper_bound_is_phase1_handshake h)    (ht : glove_number_complete_graph_upper_bound_inv1 t) :    handshake_is_clean h t := by  rcases hh with ⟨i, j, hij, rfl⟩  dsimp [handshake_is_clean]  exact ⟨hij, ht.2 i, ht.2 j⟩lemma glove_number_complete_graph_upper_bound_phase1_step_inv {m : ℕ}    {h : Handshake (Fin (m + 1)) (Fin m)} {t : Fin m × Bool → Set (Fin (m + 1))}    (hh : glove_number_complete_graph_upper_bound_is_phase1_handshake h)    (ht : glove_number_complete_graph_upper_bound_inv1 t) :    glove_number_complete_graph_upper_bound_inv1 (handshake_update_contam h t) := by  rcases hh with ⟨i, j, hij, rfl⟩  constructor  · intro k    change (if (k, false) = (i, true) then t (i, true) ∪ {i.castSucc}            else if (k, false) = (j, true) then t (j, true) ∪ {j.castSucc}            else if (k, false) = (i, false) ∨ (k, false) = (j, false) then t (i, false) ∪ t (j, false)            else t (k, false)) = ∅    have h1 : ¬ (k, false) = (i, true) := by intro h; cases h    have h2 : ¬ (k, false) = (j, true) := by intro h; cases h    rw [if_neg h1, if_neg h2]    split_ifs with h3    · rw [ht.1 i, ht.1 j, Set.union_empty]    · exact ht.1 k  · intro k    change (if (k, true) = (i, true) then t (i, true) ∪ {i.castSucc}            else if (k, true) = (j, true) then t (j, true) ∪ {j.castSucc}            else if (k, true) = (i, false) ∨ (k, true) = (j, false) then t (i, false) ∪ t (j, false)            else t (k, true)) ⊆ {k.castSucc}    split_ifs with h1 h2 h3    · injection h1 with hi      subst hi      exact Set.union_subset (ht.2 k) (Set.Subset.refl _)    · injection h2 with hj      subst hj      exact Set.union_subset (ht.2 k) (Set.Subset.refl _)    · rcases h3 with h3 | h3 <;> cases h3    · exact ht.2 klemma glove_number_complete_graph_upper_bound_phase2_step_clean {m : ℕ}    {h : Handshake (Fin (m + 1)) (Fin m)} {t : Fin m × Bool → Set (Fin (m + 1))}    (hh : glove_number_complete_graph_upper_bound_is_phase2_handshake h)    (ht : glove_number_complete_graph_upper_bound_inv2 t) :    handshake_is_clean h t := by  rcases hh with ⟨i, rfl⟩  dsimp [handshake_is_clean, opp_glove_side]  exact ⟨(ht i).1, (ht i).2⟩lemma glove_number_complete_graph_upper_bound_phase2_step_inv {m : ℕ}    {h : Handshake (Fin (m + 1)) (Fin m)} {t : Fin m × Bool → Set (Fin (m + 1))}    (hh : glove_number_complete_graph_upper_bound_is_phase2_handshake h)    (ht : glove_number_complete_graph_upper_bound_inv2 t) :    glove_number_complete_graph_upper_bound_inv2 (handshake_update_contam h t) := by  rcases hh with ⟨i, rfl⟩  intro k  constructor  · change (if (k, false) = (i, false) then t (i, false) ∪ {Fin.last m}            else if (k, false) = (i, true) then t (i, true) ∪ {i.castSucc}            else t (k, false)) ⊆ {Fin.last m}    split_ifs with h1 h2    · injection h1 with hi      subst hi      exact Set.union_subset (ht k).1 (Set.Subset.refl _)    · cases h2    · exact (ht k).1  · change (if (k, true) = (i, false) then t (i, false) ∪ {Fin.last m}            else if (k, true) = (i, true) then t (i, true) ∪ {i.castSucc}            else t (k, true)) ⊆ {k.castSucc}    split_ifs with h1 h2    · cases h1    · injection h2 with hi      subst hi      exact Set.union_subset (ht k).2 (Set.Subset.refl _)    · exact (ht k).2lemma glove_number_complete_graph_upper_bound_clean_seq_phase2 {m : ℕ}    (seq : List (Handshake (Fin (m + 1)) (Fin m)))    (hseq : ∀ h ∈ seq, glove_number_complete_graph_upper_bound_is_phase2_handshake h)    {t} (ht : glove_number_complete_graph_upper_bound_inv2 t) :    CleanHandshakeSeq seq t := by  induction seq generalizing t with  | nil => exact CleanHandshakeSeq.nil t  | cons h rest ih =>    have hh : glove_number_complete_graph_upper_bound_is_phase2_handshake h := hseq h List.mem_cons_self    have hrest : ∀ h' ∈ rest, glove_number_complete_graph_upper_bound_is_phase2_handshake h' :=      fun h' mh' => hseq h' (List.mem_cons_of_mem _ mh')    have hc := glove_number_complete_graph_upper_bound_phase2_step_clean hh ht    have hi := glove_number_complete_graph_upper_bound_phase2_step_inv hh ht    exact CleanHandshakeSeq.cons h rest t hc (ih hrest hi)lemma glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2 {m : ℕ}    (seq1 seq2 : List (Handshake (Fin (m + 1)) (Fin m)))    (hseq1 : ∀ h ∈ seq1, glove_number_complete_graph_upper_bound_is_phase1_handshake h)    (hseq2 : ∀ h ∈ seq2, glove_number_complete_graph_upper_bound_is_phase2_handshake h)    {t} (ht : glove_number_complete_graph_upper_bound_inv1 t) :    CleanHandshakeSeq (seq1 ++ seq2) t := by  induction seq1 generalizing t with  | nil =>    exact glove_number_complete_graph_upper_bound_clean_seq_phase2 seq2 hseq2      (glove_number_complete_graph_upper_bound_inv1_imp_inv2 ht)  | cons h rest ih =>    have hh : glove_number_complete_graph_upper_bound_is_phase1_handshake h := hseq1 h List.mem_cons_self    have hrest : ∀ h' ∈ rest, glove_number_complete_graph_upper_bound_is_phase1_handshake h' :=      fun h' mh' => hseq1 h' (List.mem_cons_of_mem _ mh')    have hc := glove_number_complete_graph_upper_bound_phase1_step_clean hh ht    have hi := glove_number_complete_graph_upper_bound_phase1_step_inv hh ht    exact CleanHandshakeSeq.cons h (rest ++ seq2) t hc (ih hrest hi)def glove_number_complete_graph_upper_bound_phase1 (m : ℕ) :    List (Handshake (Fin (m + 1)) (Fin m)) :=  (List.finRange m).flatMap fun i =>    (List.finRange m).filterMap fun j =>      if _h : i ≠ j then        some (Handshake.double i.castSucc (i, true) (j, true) j.castSucc)      else nonedef glove_number_complete_graph_upper_bound_phase2 (m : ℕ) :    List (Handshake (Fin (m + 1)) (Fin m)) :=  (List.finRange m).map fun i =>    Handshake.single (Fin.last m) (i, false) i.castSucclemma glove_number_complete_graph_upper_bound_phase1_all_is_phase1 (m : ℕ) :    ∀ h ∈ glove_number_complete_graph_upper_bound_phase1 m,      glove_number_complete_graph_upper_bound_is_phase1_handshake h := by  intro h hh  dsimp [glove_number_complete_graph_upper_bound_phase1] at hh  rw [List.mem_flatMap] at hh  rcases hh with ⟨i, _, hi⟩  rw [List.mem_filterMap] at hi  rcases hi with ⟨j, _, hj⟩  split_ifs at hj with hij  · injection hj with heq    subst heq    exact ⟨i, j, hij, rfl⟩lemma glove_number_complete_graph_upper_bound_phase2_all_is_phase2 (m : ℕ) :    ∀ h ∈ glove_number_complete_graph_upper_bound_phase2 m,      glove_number_complete_graph_upper_bound_is_phase2_handshake h := by  intro h hh  dsimp [glove_number_complete_graph_upper_bound_phase2] at hh  rw [List.mem_map] at hh  rcases hh with ⟨i, _, rfl⟩  exact ⟨i, rfl⟩lemma glove_number_complete_graph_upper_bound_mem_phase1 {m : ℕ} {i j : Fin m} (hij : i ≠ j) :    Handshake.double i.castSucc (i, true) (j, true) j.castSucc ∈      glove_number_complete_graph_upper_bound_phase1 m := by  dsimp [glove_number_complete_graph_upper_bound_phase1]  rw [List.mem_flatMap]  refine ⟨i, List.mem_finRange i, ?_⟩  rw [List.mem_filterMap]  refine ⟨j, List.mem_finRange j, ?_⟩  simp [hij]lemma glove_number_complete_graph_upper_bound_mem_phase2 {m : ℕ} (i : Fin m) :    Handshake.single (Fin.last m) (i, false) i.castSucc ∈      glove_number_complete_graph_upper_bound_phase2 m := by  dsimp [glove_number_complete_graph_upper_bound_phase2]  rw [List.mem_map]  exact ⟨i, List.mem_finRange i, rfl⟩lemma glove_number_complete_graph_upper_bound_edges_covered (m : ℕ) (e : Sym2 (Fin (m + 1)))    (he : e ∈ (SimpleGraph.completeGraph (Fin (m + 1))).edgeSet) :    ∃ h ∈ glove_number_complete_graph_upper_bound_phase1 m ++      glove_number_complete_graph_upper_bound_phase2 m, handshake_edge h = e := by  induction e using Sym2.inductionOn with  | hf u v =>    have huv : u ≠ v := he    rcases Fin.eq_castSucc_or_eq_last u with (⟨i, rfl⟩ | rfl)    · rcases Fin.eq_castSucc_or_eq_last v with (⟨j, rfl⟩ | rfl)      · have hij : i ≠ j := by          intro h; apply huv; subst h; rfl        refine ⟨Handshake.double i.castSucc (i, true) (j, true) j.castSucc, ?_, rfl⟩        exact List.mem_append_left _ (glove_number_complete_graph_upper_bound_mem_phase1 hij)      · refine ⟨Handshake.single (Fin.last m) (i, false) i.castSucc, ?_, ?_⟩        · exact List.mem_append_right _ (glove_number_complete_graph_upper_bound_mem_phase2 i)        · dsimp [handshake_edge]; rw [Sym2.eq_swap]    · rcases Fin.eq_castSucc_or_eq_last v with (⟨j, rfl⟩ | rfl)      · refine ⟨Handshake.single (Fin.last m) (j, false) j.castSucc, ?_, rfl⟩        exact List.mem_append_right _ (glove_number_complete_graph_upper_bound_mem_phase2 j)      · contradictionlemma glove_number_complete_graph_upper_bound_has_clean_seq (m : ℕ) :    has_clean_handshake_seq (SimpleGraph.completeGraph (Fin (m + 1))) m := by  use glove_number_complete_graph_upper_bound_phase1 m ++      glove_number_complete_graph_upper_bound_phase2 m  constructor  · have hinit : glove_number_complete_graph_upper_bound_inv1        (fun (_ : Fin m × Bool) => (∅ : Set (Fin (m + 1)))) := by      constructor      · intro k; rfl      · intro k; exact Set.empty_subset _    exact glove_number_complete_graph_upper_bound_clean_seq_phase1_then_phase2      (glove_number_complete_graph_upper_bound_phase1 m)      (glove_number_complete_graph_upper_bound_phase2 m)      (glove_number_complete_graph_upper_bound_phase1_all_is_phase1 m)      (glove_number_complete_graph_upper_bound_phase2_all_is_phase2 m)      hinit  · intro e he    exact glove_number_complete_graph_upper_bound_edges_covered m e he/-- Upper bound: gl(K_n) <= n - 1 for all n >= 2. -/theorem glove_number_complete_graph_upper_bound (n : ℕ) (hn : 2 ≤ n) : glove_number (SimpleGraph.completeGraph (Fin n)) ≤ n - 1 := by  obtain ⟨m, hm⟩ : ∃ m, n = m + 1 := Nat.exists_eq_succ_of_ne_zero (by omega)  subst hm  simp only [Nat.add_sub_cancel]  have hseq := glove_number_complete_graph_upper_bound_has_clean_seq m  exact Nat.sInf_le hseq
See it in the graphDiscuss this resultChallenge it