op_193_hom_cycle_step
For all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the G-stable Kneser graph KG(C_r ⊔ K_1, k-1).
Statement
theorem op_193_hom_cycle_step (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) :
Nonempty (GStableKneser ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)) k →g
GStableKneser ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)) (k - 1))- Formalizes
- arXiv:2610.17884 Lemma 2.12 -- The chromatic number of G-stable Kneser graphs
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- GStableKneserFor a simple graph G and a natural number k, the G-stable Kneser graph KG(G, k) is the simple graph whose vertices are the independent…
- g_stable_kneser_adjTwo independent k-sets s and t in the G-stable Kneser graph KG(G, k) are adjacent if and only if their underlying vertex sets are disjoint…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- op_193_chromaticNumber_le_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, the chromatic number of the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) is at most the chromatic…
Read back from the Lean
For all natural numbers $k$ and $r$, assuming $2 \le k$ and $2k - 2 \le r$, there exists a graph homomorphism from the stable Kneser graph with parameter $k$ of the disjoint union of the cycle graph on $r + 2$ vertices and an isolated vertex ($C_{r+2} \sqcup K_1$) to the stable Kneser graph with parameter $k - 1$ of the disjoint union of the cycle graph on $r$ vertices and an isolated vertex ($C_r \sqcup K_1$).
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
We construct a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to KG(C_r ⊔ K_1, k-1). Given an independent k-set s in C_{r+2} ⊔ K_1 with k ≥ 2, at least one vertex of s lies in C_{r+2}. We delete the maximum cycle vertex m from s and map the remaining vertices to C_r ⊔ K_1 via an embedding that fixes the isolated vertex and preserves cycle indices strictly less than r. Because every remaining cycle vertex is strictly smaller than m in an independent set of C_{r+2}, its index is strictly less than r, where the embedding is injective and introduces no new cycle adjacencies, thereby preserving independence and disjointness.
Any independent k-set in C_{r+2} ⊔ K_1 with k ≥ 2 contains at least one vertex in C_{r+2}.
We argue by contradiction using Finset.nonempty_iff_ne_empty. If the preimage under the inclusion of the cycle graph were empty, all elements of s would belong to the singleton component K_1, giving |s| ≤ 1 by Finset.card_le_card and Finset.card_singleton, which contradicts k ≥ 2.
uses
Finset.nonempty_iff_ne_empty,Finset.card_le_card,Finset.card_singletonby_contra h rw [Finset.nonempty_iff_ne_empty, not_not] at h have : s ⊆ {Sum.inr ()} := by intro x hx cases x with | inl u => have hu : u ∈ s.preimage Sum.inl Sum.inl_injective.injOn := by simp [hx] rw [h] at hu; simp at hu | inr u => cases u; simp have hcard := Finset.card_le_card this simp only [Finset.card_singleton] at hcard omega
In an independent set C of C_{r+2}, any element strictly smaller than another element m ∈ C has index strictly less than r.
We argue by contradiction. If u ≥ r, then because u < m < r + 2, the only possibility is u = r and m = r + 1. Using SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, and Nat.mod_eq_of_lt, we see that u and m are adjacent in C_{r+2}. But C is independent and u ≠ m by lt_irrefl, which is a contradiction.
uses
SimpleGraph.cycleGraph_adj',Fin.val_sub,Nat.add_mod_left,Nat.mod_eq_of_lt,lt_irreflby_contra hge have hu_lt := u.isLt have hm_lt := m.isLt have hu_val : u.val = r := by omega have hm_val : m.val = r + 1 := by omega have hadj : (SimpleGraph.cycleGraph (r + 2)).Adj u m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have h1 : (r + 2 - u.val + m.val) % (r + 2) = 1 := by rw [hu_val, hm_val] have : r + 2 - r + (r + 1) = (r + 2) + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact h1 have hpair : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u m := by apply hC_indep hu hm intro h_eq rw [h_eq] at hlt exact lt_irrefl _ hlt exact hpair hadj
The embedding op_193_embed is injective on any subset whose cycle elements are strictly less than r.
We analyze cases on x, y in s. The map preserves the distinction between cycle and isolated components. On two cycle elements u and v with values less than r, op_193_embed uses the first branch by dif_pos, preserving their numeric values, so equal images imply u.val = v.val by Fin.mk.inj, whence u = v by Fin.ext and congrArg.
uses
op_193_embed,dif_pos,Fin.mk.inj,Fin.ext,congrArgintro x hx y hy hxy cases x with | inr u => cases u cases y with | inr v => cases v; rfl | inl v => dsimp [op_193_embed] at hxy split_ifs at hxy | inl u => cases y with | inr v => cases v dsimp [op_193_embed] at hxy split_ifs at hxy | inl v => have hu := hs (Sum.inl u) hx u rfl have hv := hs (Sum.inl v) hy v rfl dsimp [op_193_embed] at hxy rw [dif_pos hu, dif_pos hv] at hxy injection hxy with h1 have hval : u.val = v.val := Fin.mk.inj h1 exact congrArg Sum.inl (Fin.ext hval)
The isolated vertex inr () has no incident edges in G ⊕ ⊥_Unit.
By definition of the disjoint union of graphs SimpleGraph.sum, there are no cross-edges between G and the Unit component, and the Unit component has the empty graph ⊥ with no edges.
uses
SimpleGraph.sumcases x <;> simp [SimpleGraph.sum] lemma op_193_sum_unit_not_adj_inr' {V : Type*} (G : SimpleGraph V) (x : V ⊕ Unit) : ¬ (G.sum (⊥ : SimpleGraph Unit)).Adj x (Sum.inr ()) := by cases x <;> simp [SimpleGraph.sum]
Adjacency of u < v in C_r is equivalent to v - u = 1 or (u = 0 and v = r - 1).
By SimpleGraph.cycleGraph_adj' and Fin.val_sub, adjacency in C_r requires the cyclic difference to be 1. Using modular arithmetic lemmas Nat.add_mod_left and Nat.mod_eq_of_lt, the two modular terms reduce to v.val - u.val and r - (v.val - u.val), which equal 1 precisely when v - u = 1 or u = 0 and v = r - 1.
uses
SimpleGraph.cycleGraph_adj',Fin.val_sub,Nat.add_mod_left,Nat.mod_eq_of_lthave hadj_iff : (SimpleGraph.cycleGraph r).Adj ⟨u.val, hu_lt⟩ ⟨v.val, hv_lt⟩ ↔ v.val - u.val = 1 ∨ (u.val = 0 ∧ v.val = r - 1) := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have h1 : (r - u.val + v.val) % r = v.val - u.val := by have : r - u.val + v.val = r + (v.val - u.val) := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have h2 : (r - v.val + u.val) % r = r - (v.val - u.val) := by have : r - v.val + u.val = r - (v.val - u.val) := by omega rw [this, Nat.mod_eq_of_lt (by omega)] rw [h1, h2] constructor · rintro (h | h) · right; omega · left; exact h · rintro (h | ⟨h0, hr1⟩) · right; exact h · left; omega
Non-maximum elements of C cannot have difference 1, so they are not adjacent in C_r via consecutive indices.
If v.val - u.val = 1, then by SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, and Nat.mod_eq_of_lt, u and v would be adjacent in C_{r+2}. Since C is independent and u ≠ v by lt_irrefl, this is impossible.
uses
SimpleGraph.cycleGraph_adj',Fin.val_sub,Nat.add_mod_left,Nat.mod_eq_of_lt,lt_irreflrw [hadj_iff] rintro (h1 | ⟨h0, hr1⟩) · have hadj_C : (SimpleGraph.cycleGraph (r + 2)).Adj u v := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - u.val + v.val) % (r + 2) = 1 := by have : r + 2 - u.val + v.val = (r + 2) + (v.val - u.val) := by omega rw [this, h1, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u v := by apply hC_indep hu hv intro heq rw [heq] at huv exact lt_irrefl _ huv exact hnot hadj_C
Non-maximum elements of C cannot be 0 and r - 1, so they are not adjacent in C_r via the wrap-around edge.
If u = 0 and v = r - 1, since v < m by lt_of_le_of_ne and m < r + 2, m must be r or r + 1. If m = r, then v and m are adjacent in C_{r+2} by SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, and Nat.mod_eq_of_lt. If m = r + 1, then u and m are adjacent in C_{r+2} by Nat.mod_eq_of_lt. In either case, this contradicts the independence of C.
uses
lt_of_le_of_ne,SimpleGraph.cycleGraph_adj',Fin.val_sub,Nat.add_mod_left,Nat.mod_eq_of_lt· have hvm_lt : v < m := lt_of_le_of_ne (hmax v hv) hvm have hm_val : m.val = r ∨ m.val = r + 1 := by have := m.isLt omega rcases hm_val with hm_r | hm_r1 · have hadj_vm : (SimpleGraph.cycleGraph (r + 2)).Adj v m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - v.val + m.val) % (r + 2) = 1 := by have : r + 2 - v.val + m.val = (r + 2) + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj v m := by apply hC_indep hv hm intro heq exact hvm heq exact hnot hadj_vm · have hadj_um : (SimpleGraph.cycleGraph (r + 2)).Adj u m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - m.val + u.val) % (r + 2) = 1 := by have : r + 2 - m.val + u.val = 1 := by omega rw [this, Nat.mod_eq_of_lt (by omega)] left; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u m := by apply hC_indep hu hm intro heq exact hum heq exact hnot hadj_um
For vertices with cycle indices strictly less than r, op_193_embed a = op_193_embed b if and only if a = b.
The reverse direction is trivial reflexivity. For the forward direction, case analysis on a and b mirrors the injectivity proof: cycle elements are identified via dif_pos, Fin.mk.inj, Fin.ext, and congrArg, while cross-component equalities are ruled out by definition of op_193_embed.
uses
op_193_embed,dif_pos,Fin.mk.inj,Fin.ext,congrArgconstructor · intro h cases a with | inr u => cases u cases b with | inr v => cases v; rfl | inl v => dsimp [op_193_embed] at h split_ifs at h | inl u => cases b with | inr v => cases v dsimp [op_193_embed] at h split_ifs at h | inl v => have hua := ha u rfl have hub := hb v rfl dsimp [op_193_embed] at h rw [dif_pos hua, dif_pos hub] at h injection h with h1 have hval : u.val = v.val := Fin.mk.inj h1 exact congrArg Sum.inl (Fin.ext hval) · rintro rfl; rfl
Definition of the map op_193_fn: deleting the maximum cycle element of s and applying op_193_embed. automation
The cycle part of s is nonempty by op_193_inlPart_nonempty. We delete its maximum element m and map the remaining set under op_193_embed. Linear arithmetic (omega) verifies 0 < r.
uses
op_193_inlPart_nonempty,op_193_embedhave hr_pos : 0 < r := by omega let C := s.1.preimage Sum.inl Sum.inl_injective.injOn have hC_ne : C.Nonempty := op_193_inlPart_nonempty hk s.1 s.2.card_eq let m := C.max' hC_ne (s.1.erase (Sum.inl m)).image (op_193_embed r hr_pos)
The reduced set s \ {m} has cardinality k - 1 and all its cycle elements have value strictly less than r, so op_193_fn s has cardinality k - 1.
Since m belongs to the cycle part of s by Finset.max'_mem and Finset.mem_preimage, erasing it decreases the cardinality by 1 using Finset.card_erase_of_mem. For any remaining cycle element u in s \ {m} (characterized by Finset.mem_erase and Finset.mem_coe), u < m by Finset.le_max' and lt_of_le_of_ne. Hence u.val < r by op_193_cycle_indep_lt_r. Injectivity of op_193_embed via op_193_embed_inj_on ensures that the image in op_193_fn has cardinality k - 1 by Finset.card_image_of_injOn.
uses
op_193_inlPart_nonempty,Finset.mem_preimage,Finset.max'_mem,Finset.card_erase_of_mem,Finset.mem_coe,Finset.mem_erase,Finset.le_max',lt_of_le_of_ne,op_193_cycle_indep_lt_r,op_193_fn,op_193_embed_inj_on,Finset.card_image_of_injOnhave hr_pos : 0 < r := by omega have hr2 : 2 ≤ r := by omega let C := s.1.preimage Sum.inl Sum.inl_injective.injOn have hC_ne : C.Nonempty := op_193_inlPart_nonempty hk s.1 s.2.card_eq let m := C.max' hC_ne have hm_in : Sum.inl m ∈ s.1 := Finset.mem_preimage.mp (Finset.max'_mem C hC_ne) let s' := s.1.erase (Sum.inl m) have hs'_card : s'.card = k - 1 := by rw [Finset.card_erase_of_mem hm_in, s.2.card_eq] have hs_cycle_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet (C : Set (Fin (r + 2))) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_preimage] at hu hv have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl u) (Sum.inl v) := s.2.isIndepSet hu hv (by rintro ⟨⟩; exact huv rfl) exact this have hs'_lt : ∀ x ∈ s', ∀ u : Fin (r + 2), x = Sum.inl u → u.val < r := by intro x hx u hxu rw [Finset.mem_erase] at hx have hu_in : u ∈ C := by rw [Finset.mem_preimage, ← hxu] exact hx.2 have hu_ne : u ≠ m := by rintro rfl exact hx.1 (by rw [hxu]) have hu_le := Finset.le_max' C u hu_in have hu_lt : u < m := lt_of_le_of_ne hu_le hu_ne exact op_193_cycle_indep_lt_r hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) hu_in hu_lt have ht_card : (op_193_fn k r hk hr s).card = k - 1 := by dsimp [op_193_fn] have hinj : Set.InjOn (op_193_embed r hr_pos) ↑s' := op_193_embed_inj_on hr_pos (↑s') (fun x hx u hxu => hs'_lt x (Finset.mem_coe.mp hx) u hxu) rw [Finset.card_image_of_injOn hinj, hs'_card] refine ⟨?_, ht_card⟩
The image op_193_fn s is an independent set in C_r ⊔ K_1.
Take distinct elements x, y in op_193_fn s, coming from a, b in s \ {m} via Finset.mem_image and Finset.mem_coe. If either vertex is the isolated vertex, it has no incident edges by op_193_sum_unit_not_adj_inr or op_193_sum_unit_not_adj_inr'. If both are cycle elements ua, ub, their cycle values are strictly less than r and both are distinct from m by Finset.mem_erase and congrArg. By lt_or_gt_of_ne and op_193_cycle_indep_step with Finset.max'_mem and Finset.le_max', ua and ub are not adjacent in C_r. Hence the image is independent in SimpleGraph.sum.
uses
Finset.mem_coe,op_193_fn,Finset.mem_image,op_193_embed,op_193_sum_unit_not_adj_inr,op_193_sum_unit_not_adj_inr',dif_pos,SimpleGraph.sum,Finset.mem_preimage,Finset.mem_erase,congrArg,lt_or_gt_of_ne,op_193_cycle_indep_step,Finset.max'_mem,Finset.le_max'intro x hx y hy hxy rw [Finset.mem_coe] at hx hy change x ∈ op_193_fn k r hk hr s at hx change y ∈ op_193_fn k r hk hr s at hy dsimp [op_193_fn] at hx hy rw [Finset.mem_image] at hx hy rcases hx with ⟨a, ha, rfl⟩ rcases hy with ⟨b, hb, rfl⟩ have hab : a ≠ b := by rintro rfl exact hxy rfl cases a with | inr ua => cases ua dsimp [op_193_embed] exact op_193_sum_unit_not_adj_inr _ _ | inl ua => cases b with | inr ub => cases ub dsimp [op_193_embed] exact op_193_sum_unit_not_adj_inr' _ _ | inl ub => have hua_lt := hs'_lt (Sum.inl ua) ha ua rfl have hub_lt := hs'_lt (Sum.inl ub) hb ub rfl dsimp [op_193_embed] rw [dif_pos hua_lt, dif_pos hub_lt] rw [SimpleGraph.sum] dsimp have hua_in : ua ∈ C := by rw [Finset.mem_preimage] exact (Finset.mem_erase.mp ha).2 have hub_in : ub ∈ C := by rw [Finset.mem_preimage] exact (Finset.mem_erase.mp hb).2 have hua_ne : ua ≠ m := by intro heq have := (Finset.mem_erase.mp ha).1 exact this (congrArg Sum.inl heq) have hub_ne : ub ≠ m := by intro heq have := (Finset.mem_erase.mp hb).1 exact this (congrArg Sum.inl heq) have huab : ua ≠ ub := by intro heq exact hab (congrArg Sum.inl heq) rcases lt_or_gt_of_ne huab with hlt | hgt · exact op_193_cycle_indep_step hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) (Finset.le_max' C) hua_in hub_in hua_ne hub_ne hlt hua_lt hub_lt · intro hadj have hadj_symm := hadj.symm exact op_193_cycle_indep_step hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) (Finset.le_max' C) hub_in hua_in hub_ne hua_ne hgt hub_lt hua_lt hadj_symm
Define the map F between the vertices of the G-stable Kneser graphs.
Each independent k-set s in C_{r+2} ⊔ K_1 is sent to op_193_fn s, which is an independent (k-1)-set in C_r ⊔ K_1 by op_193_fn_isNIndepSet.
uses
op_193_fn,op_193_fn_isNIndepSethave hr_pos : 0 < r := by omega have hr2 : 2 ≤ r := by omega let F : { s : Finset (Fin (r + 2) ⊕ Unit) // ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s } → { t : Finset (Fin r ⊕ Unit) // ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)).IsNIndepSet (k - 1) t } := fun s => ⟨op_193_fn k r hk hr s, op_193_fn_isNIndepSet k r hk hr s⟩ refine ⟨⟨F, ?_⟩⟩
The images of adjacent sets s and t under op_193_fn are disjoint.
By g_stable_kneser_adj, s and t are disjoint. If z belongs to both images (by Finset.disjoint_left and Finset.mem_image), then z = op_193_embed a = op_193_embed b for a ∈ s \ {m_s} and b ∈ t \ {m_t}. Using Finset.mem_erase, Finset.mem_preimage, op_193_inlPart_nonempty, Finset.le_max', lt_of_le_of_ne, Finset.mem_coe, Finset.max'_mem, and op_193_cycle_indep_lt_r, every cycle element in these reduced sets has value strictly less than r. Then op_193_embed_eq_iff forces a = b, so a ∈ s ∩ t, contradicting disjointness of s and t.
uses
g_stable_kneser_adj,Finset.disjoint_left,op_193_fn,Finset.mem_image,Finset.mem_erase,Finset.mem_preimage,op_193_inlPart_nonempty,Finset.le_max',lt_of_le_of_ne,Finset.mem_coe,op_193_cycle_indep_lt_r,Finset.max'_mem,op_193_embed_eq_iffintro s t hadj rw [g_stable_kneser_adj] at hadj ⊢ have hdisj : Disjoint s.1 t.1 := hadj.1 have hdisj' : Disjoint (op_193_fn k r hk hr s) (op_193_fn k r hk hr t) := by rw [Finset.disjoint_left] intro z hz1 hz2 dsimp [op_193_fn] at hz1 hz2 rw [Finset.mem_image] at hz1 hz2 rcases hz1 with ⟨a, ha, rfl⟩ rcases hz2 with ⟨b, hb, hzb⟩ have ha_in : a ∈ s.1 := (Finset.mem_erase.mp ha).2 have hb_in : b ∈ t.1 := (Finset.mem_erase.mp hb).2 have ha_lt : ∀ u : Fin (r + 2), a = Sum.inl u → u.val < r := by intro u hu have hu_in : u ∈ s.1.preimage Sum.inl Sum.inl_injective.injOn := by rw [Finset.mem_preimage, ← hu]; exact ha_in have hu_ne : u ≠ (s.1.preimage Sum.inl Sum.inl_injective.injOn).max' (op_193_inlPart_nonempty hk s.1 s.2.card_eq) := by rintro rfl exact (Finset.mem_erase.mp ha).1 (by rw [hu]) have hu_le := Finset.le_max' _ u hu_in have hu_lt' : u < _ := lt_of_le_of_ne hu_le hu_ne have hs_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet ((s.1.preimage Sum.inl Sum.inl_injective.injOn : Finset (Fin (r + 2))) : Set (Fin (r + 2))) := by intro x hx y hy hxy rw [Finset.mem_coe, Finset.mem_preimage] at hx hy have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl x) (Sum.inl y) := s.2.isIndepSet hx hy (by rintro ⟨⟩; exact hxy rfl) exact this exact op_193_cycle_indep_lt_r hr2 _ hs_indep (Finset.max'_mem _ _) hu_in hu_lt' have hb_lt : ∀ u : Fin (r + 2), b = Sum.inl u → u.val < r := by intro u hu have hu_in : u ∈ t.1.preimage Sum.inl Sum.inl_injective.injOn := by rw [Finset.mem_preimage, ← hu]; exact hb_in have hu_ne : u ≠ (t.1.preimage Sum.inl Sum.inl_injective.injOn).max' (op_193_inlPart_nonempty hk t.1 t.2.card_eq) := by rintro rfl exact (Finset.mem_erase.mp hb).1 (by rw [hu]) have hu_le := Finset.le_max' _ u hu_in have hu_lt' : u < _ := lt_of_le_of_ne hu_le hu_ne have ht_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet ((t.1.preimage Sum.inl Sum.inl_injective.injOn : Finset (Fin (r + 2))) : Set (Fin (r + 2))) := by intro x hx y hy hxy rw [Finset.mem_coe, Finset.mem_preimage] at hx hy have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl x) (Sum.inl y) := t.2.isIndepSet hx hy (by rintro ⟨⟩; exact hxy rfl) exact this exact op_193_cycle_indep_lt_r hr2 _ ht_indep (Finset.max'_mem _ _) hu_in hu_lt' have heq : a = b := (op_193_embed_eq_iff hr_pos a b ha_lt hb_lt).mp hzb.symm rw [heq] at ha_in exact (Finset.disjoint_left.mp hdisj ha_in) hb_in
The images F(s) and F(t) are distinct, completing the homomorphism proof.
Since the image has cardinality k - 1 ≥ 1 by op_193_fn_isNIndepSet and Finset.card_empty, it is nonempty by Finset.nonempty_iff_ne_empty. If F(s) = F(t), taking the underlying values via Subtype.val would give op_193_fn s = op_193_fn t, so any element in F(s) would belong to both images, contradicting their disjointness via Finset.disjoint_left.
uses
op_193_fn,op_193_fn_isNIndepSet,Finset.nonempty_iff_ne_empty,Finset.card_empty,congrArg,Subtype.val,Finset.disjoint_leftrefine ⟨hdisj', ?_⟩ rintro heq have hcard : (op_193_fn k r hk hr s).card = k - 1 := (op_193_fn_isNIndepSet k r hk hr s).card_eq have hne : (op_193_fn k r hk hr s).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro he rw [he, Finset.card_empty] at hcard omega rcases hne with ⟨x, hx_s⟩ have heq1 : (F s).1 = (F t).1 := congrArg Subtype.val heq change op_193_fn k r hk hr s = op_193_fn k r hk hr t at heq1 have hx_t : x ∈ op_193_fn k r hk hr t := by rw [← heq1]; exact hx_s exact (Finset.disjoint_left.mp hdisj' hx_s) hx_t
Finset.card_empty- The empty set of a finite set has cardinality 0.
Finset.card_erase_of_mem- Erasing an element from a finite set decreases its cardinality by 1.
Finset.card_image_of_injOn- If a function is injective on a finite set s, the cardinality of its image equals the cardinality of s.
Finset.card_le_card- A subset of a finite set has cardinality at most the cardinality of the ambient set.
Finset.card_singleton- A singleton finite set has cardinality 1.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Finset.le_max'- Every element of a finite set is less than or equal to the maximum element of that set.
Finset.max'_mem- The maximum element of a nonempty finite set belongs to the set.
Finset.mem_coe- Coercion of a finite set to a set preserves membership.
Finset.mem_erase- An element belongs to a finite set with an element erased if and only if it is distinct from the erased element and belongs to the original set.
Finset.mem_image- An element belongs to the image of a set under f if and only if it is the image of some element of the set.
Finset.mem_preimage- An element belongs to the preimage of a set under f if and only if its image under f belongs to the set.
Fin.mk.inj- Equality of constructor instances of Fin implies equality of the underlying natural numbers.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not the empty set.
Fin.val_sub- The integer value of the modular subtraction of two elements in Fin n is (n - b + a) % n.
Nat.add_mod_left- For natural numbers x and z, (x + z) % x = z % x.
Nat.mod_eq_of_lt- If a < b, then a % b = a for natural numbers.
g_stable_kneser_adj- Adjacency condition in the G-stable Kneser graph: two vertices are adjacent if and only if their underlying independent sets are disjoint and distinct.
lt_irrefl- Strict inequality is irreflexive: ¬(a < a).
lt_of_le_of_ne- In a partial order, a ≤ b and a ≠ b imply a < b.
lt_or_gt_of_ne- In a linear order, a ≠ b implies a < b or b < a.
op_193_embed- The canonical embedding from Fin (r+2) ⊕ Unit to Fin r ⊕ Unit, fixing the Unit component and mapping cycle indices strictly bounded by r to the same index.
op_193_embed_inj_on- The embedding op_193_embed is injective on any set whose cycle elements have values strictly less than r.
op_193_embed_eq_iff- For vertices whose cycle components are strictly less than r, their images under op_193_embed are equal if and only if the vertices are equal.
op_193_cycle_indep_lt_r- In any independent set of C_{r+2}, any element strictly smaller than another element in the set has index strictly less than r.
op_193_cycle_indep_step- Non-maximum elements of an independent set in C_{r+2} with cycle indices less than r cannot be adjacent in C_r.
op_193_fn- The reduction map that deletes the maximum cycle vertex of an independent k-set in C_{r+2} ⊔ K_1 and applies the embedding to the remaining vertices.
op_193_fn_isNIndepSet- The set produced by op_193_fn is an independent (k-1)-set in C_r ⊔ K_1.
op_193_inlPart_nonempty- Any k-element subset of C_{r+2} ⊔ K_1 with k ≥ 2 contains at least one vertex from C_{r+2}.
op_193_sum_unit_not_adj_inr- In the disjoint union G ⊕ ⊥_Unit, the isolated vertex is not adjacent to any vertex.
op_193_sum_unit_not_adj_inr'- In the disjoint union G ⊕ ⊥_Unit, no vertex is adjacent to the isolated vertex.
SimpleGraph.cycleGraph_adj'- Two vertices in the cycle graph C_n are adjacent if and only if their modular difference is 1.
SimpleGraph.sum- The disjoint union of two graphs, with no edges between the two components.
Subtype.val- The projection from a subtype to its underlying carrier type.
congrArg- Congruence of a function with respect to equality of arguments.
dif_pos- Evaluation of a dependent conditional when the condition is true.
- The disjoint union C_{r+2} ⊔ K_1 is formalized as SimpleGraph.sum of the cycle graph and the empty graph on the singleton type Unit (⊥ : SimpleGraph Unit).
- The helper definition op_193_fn contains a local proof of 0 < r using the omega decision procedure.
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.
open Finsetdef op_193_embed (r : ℕ) (hr : 0 < r) (x : Fin (r + 2) ⊕ Unit) : Fin r ⊕ Unit := match x with | Sum.inr () => Sum.inr () | Sum.inl u => if h : u.val < r then Sum.inl ⟨u.val, h⟩ else Sum.inl ⟨0, hr⟩lemma op_193_inlPart_nonempty {r k : ℕ} (hk : 2 ≤ k) (s : Finset (Fin (r + 2) ⊕ Unit)) (hs : s.card = k) : (s.preimage Sum.inl Sum.inl_injective.injOn).Nonempty := by by_contra h rw [Finset.nonempty_iff_ne_empty, not_not] at h have : s ⊆ {Sum.inr ()} := by intro x hx cases x with | inl u => have hu : u ∈ s.preimage Sum.inl Sum.inl_injective.injOn := by simp [hx] rw [h] at hu; simp at hu | inr u => cases u; simp have hcard := Finset.card_le_card this simp only [Finset.card_singleton] at hcard omegalemma op_193_cycle_indep_lt_r {r : ℕ} (hr : 2 ≤ r) (C : Finset (Fin (r + 2))) (hC_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet (C : Set (Fin (r + 2)))) {m u : Fin (r + 2)} (hm : m ∈ C) (hu : u ∈ C) (hlt : u < m) : u.val < r := by by_contra hge have hu_lt := u.isLt have hm_lt := m.isLt have hu_val : u.val = r := by omega have hm_val : m.val = r + 1 := by omega have hadj : (SimpleGraph.cycleGraph (r + 2)).Adj u m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have h1 : (r + 2 - u.val + m.val) % (r + 2) = 1 := by rw [hu_val, hm_val] have : r + 2 - r + (r + 1) = (r + 2) + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact h1 have hpair : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u m := by apply hC_indep hu hm intro h_eq rw [h_eq] at hlt exact lt_irrefl _ hlt exact hpair hadjlemma op_193_embed_inj_on {r : ℕ} (hr : 0 < r) (s : Set (Fin (r + 2) ⊕ Unit)) (hs : ∀ x ∈ s, ∀ u : Fin (r + 2), x = Sum.inl u → u.val < r) : s.InjOn (op_193_embed r hr) := by intro x hx y hy hxy cases x with | inr u => cases u cases y with | inr v => cases v; rfl | inl v => dsimp [op_193_embed] at hxy split_ifs at hxy | inl u => cases y with | inr v => cases v dsimp [op_193_embed] at hxy split_ifs at hxy | inl v => have hu := hs (Sum.inl u) hx u rfl have hv := hs (Sum.inl v) hy v rfl dsimp [op_193_embed] at hxy rw [dif_pos hu, dif_pos hv] at hxy injection hxy with h1 have hval : u.val = v.val := Fin.mk.inj h1 exact congrArg Sum.inl (Fin.ext hval)lemma op_193_sum_unit_not_adj_inr {V : Type*} (G : SimpleGraph V) (x : V ⊕ Unit) : ¬ (G.sum (⊥ : SimpleGraph Unit)).Adj (Sum.inr ()) x := by cases x <;> simp [SimpleGraph.sum]lemma op_193_sum_unit_not_adj_inr' {V : Type*} (G : SimpleGraph V) (x : V ⊕ Unit) : ¬ (G.sum (⊥ : SimpleGraph Unit)).Adj x (Sum.inr ()) := by cases x <;> simp [SimpleGraph.sum]lemma op_193_cycle_indep_step {r : ℕ} (hr : 2 ≤ r) (C : Finset (Fin (r + 2))) (hC_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet (C : Set (Fin (r + 2)))) {m : Fin (r + 2)} (hm : m ∈ C) (hmax : ∀ x ∈ C, x ≤ m) {u v : Fin (r + 2)} (hu : u ∈ C) (hv : v ∈ C) (hum : u ≠ m) (hvm : v ≠ m) (huv : u < v) (hu_lt : u.val < r) (hv_lt : v.val < r) : ¬ (SimpleGraph.cycleGraph r).Adj ⟨u.val, hu_lt⟩ ⟨v.val, hv_lt⟩ := by have hadj_iff : (SimpleGraph.cycleGraph r).Adj ⟨u.val, hu_lt⟩ ⟨v.val, hv_lt⟩ ↔ v.val - u.val = 1 ∨ (u.val = 0 ∧ v.val = r - 1) := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have h1 : (r - u.val + v.val) % r = v.val - u.val := by have : r - u.val + v.val = r + (v.val - u.val) := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have h2 : (r - v.val + u.val) % r = r - (v.val - u.val) := by have : r - v.val + u.val = r - (v.val - u.val) := by omega rw [this, Nat.mod_eq_of_lt (by omega)] rw [h1, h2] constructor · rintro (h | h) · right; omega · left; exact h · rintro (h | ⟨h0, hr1⟩) · right; exact h · left; omega rw [hadj_iff] rintro (h1 | ⟨h0, hr1⟩) · have hadj_C : (SimpleGraph.cycleGraph (r + 2)).Adj u v := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - u.val + v.val) % (r + 2) = 1 := by have : r + 2 - u.val + v.val = (r + 2) + (v.val - u.val) := by omega rw [this, h1, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u v := by apply hC_indep hu hv intro heq rw [heq] at huv exact lt_irrefl _ huv exact hnot hadj_C · have hvm_lt : v < m := lt_of_le_of_ne (hmax v hv) hvm have hm_val : m.val = r ∨ m.val = r + 1 := by have := m.isLt omega rcases hm_val with hm_r | hm_r1 · have hadj_vm : (SimpleGraph.cycleGraph (r + 2)).Adj v m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - v.val + m.val) % (r + 2) = 1 := by have : r + 2 - v.val + m.val = (r + 2) + 1 := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] right; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj v m := by apply hC_indep hv hm intro heq exact hvm heq exact hnot hadj_vm · have hadj_um : (SimpleGraph.cycleGraph (r + 2)).Adj u m := by rw [SimpleGraph.cycleGraph_adj', Fin.val_sub, Fin.val_sub] have : (r + 2 - m.val + u.val) % (r + 2) = 1 := by have : r + 2 - m.val + u.val = 1 := by omega rw [this, Nat.mod_eq_of_lt (by omega)] left; exact this have hnot : ¬ (SimpleGraph.cycleGraph (r + 2)).Adj u m := by apply hC_indep hu hm intro heq exact hum heq exact hnot hadj_umlemma op_193_embed_eq_iff {r : ℕ} (hr : 0 < r) (a b : Fin (r + 2) ⊕ Unit) (ha : ∀ u : Fin (r + 2), a = Sum.inl u → u.val < r) (hb : ∀ u : Fin (r + 2), b = Sum.inl u → u.val < r) : op_193_embed r hr a = op_193_embed r hr b ↔ a = b := by constructor · intro h cases a with | inr u => cases u cases b with | inr v => cases v; rfl | inl v => dsimp [op_193_embed] at h split_ifs at h | inl u => cases b with | inr v => cases v dsimp [op_193_embed] at h split_ifs at h | inl v => have hua := ha u rfl have hub := hb v rfl dsimp [op_193_embed] at h rw [dif_pos hua, dif_pos hub] at h injection h with h1 have hval : u.val = v.val := Fin.mk.inj h1 exact congrArg Sum.inl (Fin.ext hval) · rintro rfl; rflnoncomputable def op_193_fn (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) (s : { s : Finset (Fin (r + 2) ⊕ Unit) // ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s }) : Finset (Fin r ⊕ Unit) := have hr_pos : 0 < r := by omega let C := s.1.preimage Sum.inl Sum.inl_injective.injOn have hC_ne : C.Nonempty := op_193_inlPart_nonempty hk s.1 s.2.card_eq let m := C.max' hC_ne (s.1.erase (Sum.inl m)).image (op_193_embed r hr_pos)lemma op_193_fn_isNIndepSet (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) (s : { s : Finset (Fin (r + 2) ⊕ Unit) // ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s }) : ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)).IsNIndepSet (k - 1) (op_193_fn k r hk hr s) := by have hr_pos : 0 < r := by omega have hr2 : 2 ≤ r := by omega let C := s.1.preimage Sum.inl Sum.inl_injective.injOn have hC_ne : C.Nonempty := op_193_inlPart_nonempty hk s.1 s.2.card_eq let m := C.max' hC_ne have hm_in : Sum.inl m ∈ s.1 := Finset.mem_preimage.mp (Finset.max'_mem C hC_ne) let s' := s.1.erase (Sum.inl m) have hs'_card : s'.card = k - 1 := by rw [Finset.card_erase_of_mem hm_in, s.2.card_eq] have hs_cycle_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet (C : Set (Fin (r + 2))) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_preimage] at hu hv have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl u) (Sum.inl v) := s.2.isIndepSet hu hv (by rintro ⟨⟩; exact huv rfl) exact this have hs'_lt : ∀ x ∈ s', ∀ u : Fin (r + 2), x = Sum.inl u → u.val < r := by intro x hx u hxu rw [Finset.mem_erase] at hx have hu_in : u ∈ C := by rw [Finset.mem_preimage, ← hxu] exact hx.2 have hu_ne : u ≠ m := by rintro rfl exact hx.1 (by rw [hxu]) have hu_le := Finset.le_max' C u hu_in have hu_lt : u < m := lt_of_le_of_ne hu_le hu_ne exact op_193_cycle_indep_lt_r hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) hu_in hu_lt have ht_card : (op_193_fn k r hk hr s).card = k - 1 := by dsimp [op_193_fn] have hinj : Set.InjOn (op_193_embed r hr_pos) ↑s' := op_193_embed_inj_on hr_pos (↑s') (fun x hx u hxu => hs'_lt x (Finset.mem_coe.mp hx) u hxu) rw [Finset.card_image_of_injOn hinj, hs'_card] refine ⟨?_, ht_card⟩ intro x hx y hy hxy rw [Finset.mem_coe] at hx hy change x ∈ op_193_fn k r hk hr s at hx change y ∈ op_193_fn k r hk hr s at hy dsimp [op_193_fn] at hx hy rw [Finset.mem_image] at hx hy rcases hx with ⟨a, ha, rfl⟩ rcases hy with ⟨b, hb, rfl⟩ have hab : a ≠ b := by rintro rfl exact hxy rfl cases a with | inr ua => cases ua dsimp [op_193_embed] exact op_193_sum_unit_not_adj_inr _ _ | inl ua => cases b with | inr ub => cases ub dsimp [op_193_embed] exact op_193_sum_unit_not_adj_inr' _ _ | inl ub => have hua_lt := hs'_lt (Sum.inl ua) ha ua rfl have hub_lt := hs'_lt (Sum.inl ub) hb ub rfl dsimp [op_193_embed] rw [dif_pos hua_lt, dif_pos hub_lt] rw [SimpleGraph.sum] dsimp have hua_in : ua ∈ C := by rw [Finset.mem_preimage] exact (Finset.mem_erase.mp ha).2 have hub_in : ub ∈ C := by rw [Finset.mem_preimage] exact (Finset.mem_erase.mp hb).2 have hua_ne : ua ≠ m := by intro heq have := (Finset.mem_erase.mp ha).1 exact this (congrArg Sum.inl heq) have hub_ne : ub ≠ m := by intro heq have := (Finset.mem_erase.mp hb).1 exact this (congrArg Sum.inl heq) have huab : ua ≠ ub := by intro heq exact hab (congrArg Sum.inl heq) rcases lt_or_gt_of_ne huab with hlt | hgt · exact op_193_cycle_indep_step hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) (Finset.le_max' C) hua_in hub_in hua_ne hub_ne hlt hua_lt hub_lt · intro hadj have hadj_symm := hadj.symm exact op_193_cycle_indep_step hr2 C hs_cycle_indep (Finset.max'_mem C hC_ne) (Finset.le_max' C) hub_in hua_in hub_ne hua_ne hgt hub_lt hua_lt hadj_symm/-- Homomorphism from KG(C_{r+2} ⊔ K_1, k) to KG(C_r ⊔ K_1, k-1). -/theorem op_193_hom_cycle_step (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) : Nonempty (GStableKneser ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)) k →g GStableKneser ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)) (k - 1)) := by have hr_pos : 0 < r := by omega have hr2 : 2 ≤ r := by omega let F : { s : Finset (Fin (r + 2) ⊕ Unit) // ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s } → { t : Finset (Fin r ⊕ Unit) // ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)).IsNIndepSet (k - 1) t } := fun s => ⟨op_193_fn k r hk hr s, op_193_fn_isNIndepSet k r hk hr s⟩ refine ⟨⟨F, ?_⟩⟩ intro s t hadj rw [g_stable_kneser_adj] at hadj ⊢ have hdisj : Disjoint s.1 t.1 := hadj.1 have hdisj' : Disjoint (op_193_fn k r hk hr s) (op_193_fn k r hk hr t) := by rw [Finset.disjoint_left] intro z hz1 hz2 dsimp [op_193_fn] at hz1 hz2 rw [Finset.mem_image] at hz1 hz2 rcases hz1 with ⟨a, ha, rfl⟩ rcases hz2 with ⟨b, hb, hzb⟩ have ha_in : a ∈ s.1 := (Finset.mem_erase.mp ha).2 have hb_in : b ∈ t.1 := (Finset.mem_erase.mp hb).2 have ha_lt : ∀ u : Fin (r + 2), a = Sum.inl u → u.val < r := by intro u hu have hu_in : u ∈ s.1.preimage Sum.inl Sum.inl_injective.injOn := by rw [Finset.mem_preimage, ← hu]; exact ha_in have hu_ne : u ≠ (s.1.preimage Sum.inl Sum.inl_injective.injOn).max' (op_193_inlPart_nonempty hk s.1 s.2.card_eq) := by rintro rfl exact (Finset.mem_erase.mp ha).1 (by rw [hu]) have hu_le := Finset.le_max' _ u hu_in have hu_lt' : u < _ := lt_of_le_of_ne hu_le hu_ne have hs_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet ((s.1.preimage Sum.inl Sum.inl_injective.injOn : Finset (Fin (r + 2))) : Set (Fin (r + 2))) := by intro x hx y hy hxy rw [Finset.mem_coe, Finset.mem_preimage] at hx hy have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl x) (Sum.inl y) := s.2.isIndepSet hx hy (by rintro ⟨⟩; exact hxy rfl) exact this exact op_193_cycle_indep_lt_r hr2 _ hs_indep (Finset.max'_mem _ _) hu_in hu_lt' have hb_lt : ∀ u : Fin (r + 2), b = Sum.inl u → u.val < r := by intro u hu have hu_in : u ∈ t.1.preimage Sum.inl Sum.inl_injective.injOn := by rw [Finset.mem_preimage, ← hu]; exact hb_in have hu_ne : u ≠ (t.1.preimage Sum.inl Sum.inl_injective.injOn).max' (op_193_inlPart_nonempty hk t.1 t.2.card_eq) := by rintro rfl exact (Finset.mem_erase.mp hb).1 (by rw [hu]) have hu_le := Finset.le_max' _ u hu_in have hu_lt' : u < _ := lt_of_le_of_ne hu_le hu_ne have ht_indep : (SimpleGraph.cycleGraph (r + 2)).IsIndepSet ((t.1.preimage Sum.inl Sum.inl_injective.injOn : Finset (Fin (r + 2))) : Set (Fin (r + 2))) := by intro x hx y hy hxy rw [Finset.mem_coe, Finset.mem_preimage] at hx hy have : ¬ ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)).Adj (Sum.inl x) (Sum.inl y) := t.2.isIndepSet hx hy (by rintro ⟨⟩; exact hxy rfl) exact this exact op_193_cycle_indep_lt_r hr2 _ ht_indep (Finset.max'_mem _ _) hu_in hu_lt' have heq : a = b := (op_193_embed_eq_iff hr_pos a b ha_lt hb_lt).mp hzb.symm rw [heq] at ha_in exact (Finset.disjoint_left.mp hdisj ha_in) hb_in refine ⟨hdisj', ?_⟩ rintro heq have hcard : (op_193_fn k r hk hr s).card = k - 1 := (op_193_fn_isNIndepSet k r hk hr s).card_eq have hne : (op_193_fn k r hk hr s).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro he rw [he, Finset.card_empty] at hcard omega rcases hne with ⟨x, hx_s⟩ have heq1 : (F s).1 = (F t).1 := congrArg Subtype.val heq change op_193_fn k r hk hr s = op_193_fn k r hk hr t at heq1 have hx_t : x ∈ op_193_fn k r hk hr t := by rw [← heq1]; exact hx_s exact (Finset.disjoint_left.mp hdisj' hx_s) hx_t