glove_number_complete_graph_upper_bound
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
- glove_number_complete_graph_eq_iff_geFor 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$.
- glove_number_k2The glove number of the complete graph $K_2$ is equal to 1.
- glove_number_k3The glove number of the complete graph $K_3$ is equal to 2.
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.
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.
uses
Set.empty_subsetintro k constructor · rw [ht.1 k] exact Set.empty_subset _ · exact ht.2 k
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.
rcases hh with ⟨i, j, hij, rfl⟩ dsimp [handshake_is_clean] exact ⟨hij, ht.2 i, ht.2 j⟩
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.
uses
if_neg,Set.union_empty,Set.union_subset,Set.Subset.reflrcases 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
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.
rcases hh with ⟨i, rfl⟩ dsimp [handshake_is_clean, opp_glove_side] exact ⟨(ht i).1, (ht i).2⟩
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.
uses
Set.union_subset,Set.Subset.reflrcases 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
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.
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.consinduction 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)
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.
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.consinduction 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)
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.
uses
List.mem_flatMap,List.mem_filterMapintro 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⟩
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).
uses
List.mem_mapintro 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⟩
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.
uses
List.mem_flatMap,List.mem_finRange,List.mem_filterMapdsimp [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]
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.
uses
List.mem_map,List.mem_finRangedsimp [glove_number_complete_graph_upper_bound_phase2] rw [List.mem_map] exact ⟨i, List.mem_finRange i, rfl⟩
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.
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_swapinduction 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
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.
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_covereduse 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
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.
uses
Nat.exists_eq_succ_of_ne_zero,Nat.add_sub_cancel,glove_number_complete_graph_upper_bound_has_clean_seq,Nat.sInf_leobtain ⟨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.
- In this formalization, the n vertices of K_n are identified with Fin (m + 1) where m = n - 1. The first m vertices are i.castSucc for i : Fin m, and the last vertex is Fin.last m.
- Each glove k has two sides: (k, true) (used in Phase 1) and (k, false) (used in Phase 2). Contamination is tracked as a mapping from glove sides to subsets of vertices.
- The glove number is defined as the infimum of all k for which a clean handshake sequence exists, so exhibiting a clean sequence using m gloves proves that the glove number 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
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.
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