AFTD Auto-Formalizing Theoretical Domains

op_193_hom_cycle_step

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

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

    lines 13–24

    uses Finset.nonempty_iff_ne_empty, Finset.card_le_card, Finset.card_singleton

      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
      omega
  2. 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.

    lines 30–47

    uses SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, Nat.mod_eq_of_lt, lt_irrefl

      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 hadj
  3. 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.

    lines 53–75

    uses op_193_embed, dif_pos, Fin.mk.inj, Fin.ext, congrArg

      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)
  4. 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.

    lines 79–83

    uses SimpleGraph.sum

      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]
  5. 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.

    lines 92–108

    uses SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, Nat.mod_eq_of_lt

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

    lines 109–122

    uses SimpleGraph.cycleGraph_adj', Fin.val_sub, Nat.add_mod_left, Nat.mod_eq_of_lt, lt_irrefl

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

    lines 123–150

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

    lines 155–179

    uses op_193_embed, dif_pos, Fin.mk.inj, Fin.ext, congrArg

      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; rfl
  9. 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.

    lines 185–190

    uses op_193_inlPart_nonempty, op_193_embed

      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)
    
  10. 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.

    lines 196–228

    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_injOn

      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⟩
  11. 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.

    lines 229–282

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

    lines 287–294

    uses op_193_fn, op_193_fn_isNIndepSet

      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, ?_⟩⟩
  13. 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.

    lines 295–343

    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_iff

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

    lines 344–356

    uses op_193_fn, op_193_fn_isNIndepSet, Finset.nonempty_iff_ne_empty, Finset.card_empty, congrArg, Subtype.val, Finset.disjoint_left

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

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

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