AFTD Auto-Formalizing Theoretical Domains

op_193_cycle_isolated_vertex_chromatic_le

theoremverifiedformalization

For any natural numbers k ≥ 3 and m ≥ 4 * k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and an isolated vertex is at most m - 2 * k + 3.

Statement

theorem op_193_cycle_isolated_vertex_chromatic_le
    (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :
    (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber ≤
      m - 2 * k + 3
Formalizes
scout/2610-17884-the-chromatic-number-of-g-stable-kneser-graphs.md:112
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 3

Read back from the Lean

For any natural numbers $k$ and $m$ such that $3 \le k$ and $4k - 3 \le m$, the chromatic number of the generalized stable Kneser graph GStableKneser on the disjoint union of the cycle graph $C_m$ and an isolated vertex (a graph on Unit with no edges), with parameter $k$, is at most $m - 2k + 3$.

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 chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 is at most m - 2 * k + 3, we construct an explicit proper coloring using m - 2 * k + 3 colors. An independent set containing the isolated vertex is assigned the special color m - 2 * k + 2. An independent set avoiding the isolated vertex is projected to the cycle, where its color is the minimum of its elements and the cutoff value m - 2 * k + 1; disjointness and a counting argument on intervals ensure that adjacent independent sets receive distinct colors.

  1. The function Sum.inl is injective, enabling the definition of the cycle projection inlPart as a preimage.

    The preimage operation requires injectivity on the preimage set, which is immediate from the global injectivity of Sum.inl.

    lines 5–7

    uses Sum.inl_injective

      S.preimage Sum.inl (by
        intro a ha b hb hab
        exact Sum.inl_injective hab)
  2. An element of the cycle belongs to inlPart S if and only if its left-injection is in S.

    Unfolding the definition of inlPart, this is the characteristic property of preimages given by Finset.mem_preimage.

    lines 9–14

    uses Finset.mem_preimage

    lemma op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart {m : ℕ}
        (S : Finset (Fin m ⊕ Unit)) (a : Fin m) :
        a ∈ op_193_cycle_isolated_vertex_chromatic_le_inlPart S ↔ Sum.inl a ∈ S := by
      unfold op_193_cycle_isolated_vertex_chromatic_le_inlPart
      exact Finset.mem_preimage
    
  3. When the isolated vertex is not in S, the cycle projection preserves cardinality: |inlPart S| = |S|.

    Since the isolated vertex is absent, mapping inlPart S by the embedding Sum.inl recovers S exactly. Taking cardinalities on both sides and applying Finset.card_map gives the equality.

    lines 15–33

    uses Sum.inl_injective, Finset.mem_map, congrArg, Finset.card_map

    lemma op_193_cycle_isolated_vertex_chromatic_le_card_inlPart {m : ℕ}
        (S : Finset (Fin m ⊕ Unit)) (h : (Sum.inr () : Fin m ⊕ Unit) ∉ S) :
        (op_193_cycle_isolated_vertex_chromatic_le_inlPart S).card = S.card := by
      have hmap :
          (op_193_cycle_isolated_vertex_chromatic_le_inlPart S).map
            ⟨Sum.inl, Sum.inl_injective⟩ = S := by
        ext x
        rw [Finset.mem_map]
        constructor
        · rintro ⟨a, ha, rfl⟩
          exact (op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart S a).mp ha
        · intro hx
          rcases x with a | u
          · exact ⟨a, (op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart S a).mpr hx, rfl⟩
          · exact absurd hx (by simpa using h)
      have hc := congrArg Finset.card hmap
      rw [Finset.card_map] at hc
      exact hc
    
  4. If the cutoff minimums of two disjoint k-subsets A and B both equal fb, a cardinality contradiction arises. automation

    If min(A ∪ {fb}) = fb, every element of A is at least fb, so A ⊆ [fb, m - 1]. Similarly B ⊆ [fb, m - 1]. Since A and B are disjoint, their union has size 2k, but [fb, m - 1] has size m - fb = 2k - 1, which implies 2k ≤ 2k - 1, an impossibility by linear arithmetic.

    lines 63–81

    uses op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem, Finset.card_union_of_disjoint, Finset.union_subset, Finset.card_le_card, Fin.card_Ici, Finset.mem_Ici

      intro heq
      by_cases hAfb : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb = fb
      · have hBfb : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb = fb := by
          rw [← heq]; exact hAfb
        have hAsub : A ⊆ Finset.Ici fb := by
          intro a ha
          rw [Finset.mem_Ici]
          calc fb = op_193_cycle_isolated_vertex_chromatic_le_mmin A fb := hAfb.symm
            _ ≤ a := op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem ha
        have hBsub : B ⊆ Finset.Ici fb := by
          intro a ha
          rw [Finset.mem_Ici]
          calc fb = op_193_cycle_isolated_vertex_chromatic_le_mmin B fb := hBfb.symm
            _ ≤ a := op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem ha
        have hunion : (A ∪ B).card = A.card + B.card := Finset.card_union_of_disjoint hdisj
        have hunionsub : A ∪ B ⊆ Finset.Ici fb := Finset.union_subset hAsub hBsub
        have hle : (A ∪ B).card ≤ (Finset.Ici fb).card := Finset.card_le_card hunionsub
        rw [hunion, hA, hB, Fin.card_Ici, hfbval] at hle
        omega
  5. The cutoff minimums of two disjoint k-subsets A and B cannot be equal to a value strictly less than fb.

    If the common minimum is not fb, it must belong to both A and B by the definition of the minimum of A ∪ {fb} and B ∪ {fb}. But this contradicts that A and B are disjoint.

    lines 82–99

    uses op_193_cycle_isolated_vertex_chromatic_le_mmin_mem, Finset.mem_singleton, Finset.disjoint_left

      · have hBfb : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb ≠ fb := by
          rw [← heq]; exact hAfb
        have hA_mem : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ∈ A := by
          have h := op_193_cycle_isolated_vertex_chromatic_le_mmin_mem A fb
          rcases Finset.mem_union.mp h with h | h
          · exact h
          · rw [Finset.mem_singleton] at h
            exact absurd h hAfb
        have hB_mem : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb ∈ B := by
          have h := op_193_cycle_isolated_vertex_chromatic_le_mmin_mem B fb
          rcases Finset.mem_union.mp h with h | h
          · exact h
          · rw [Finset.mem_singleton] at h
            exact absurd h hBfb
        have hnot : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ∉ B :=
          Finset.disjoint_left.mp hdisj hA_mem
        exact hnot (heq ▸ hB_mem)
    
  6. The coloring colorFin assigns each k-independent set a valid color index in Fin(m - 2*k + 3). automation

    If the independent set contains the isolated vertex, it receives color m - 2*k + 2 < m - 2*k + 3. Otherwise, it receives its cutoff minimum, which is bounded above by fb = m - 2*k + 1 < m - 2*k + 3. Both inequalities are verified by linear integer arithmetic.

    lines 100–116

    uses op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le

    noncomputable def op_193_cycle_isolated_vertex_chromatic_le_colorFin (k m : ℕ)
        (hfb : m - 2*k + 1 < m)
        (v : { s : Finset (Fin m ⊕ Unit) //
          ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s }) :
        Fin (m - 2*k + 3) :=
      if hin : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1 then
        ⟨m - 2*k + 2, by omega⟩
      else
        ⟨(op_193_cycle_isolated_vertex_chromatic_le_mmin
            (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩).val, by
          have h1 : (op_193_cycle_isolated_vertex_chromatic_le_mmin
              (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)
              ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=
            op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le
              (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩
          omega⟩
    
  7. If an independent set v contains the isolated vertex, its color value is m - 2*k + 2.

    Unfolding the definition of colorFin, the then-branch is selected by dif_pos since the condition holds.

    lines 117–125

    uses dif_pos

    lemma op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem (k m : ℕ)
        (hfb : m - 2*k + 1 < m)
        (v : { s : Finset (Fin m ⊕ Unit) //
          ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s })
        (h : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1) :
        (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val = m - 2*k + 2 := by
      unfold op_193_cycle_isolated_vertex_chromatic_le_colorFin
      rw [dif_pos h]
    
  8. If an independent set v does not contain the isolated vertex, its color value is the cutoff minimum.

    Unfolding colorFin, the else-branch is selected by dif_neg since the condition fails.

    lines 126–136

    uses dif_neg

    lemma op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem (k m : ℕ)
        (hfb : m - 2*k + 1 < m)
        (v : { s : Finset (Fin m ⊕ Unit) //
          ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s })
        (h : (Sum.inr () : Fin m ⊕ Unit) ∉ v.1) :
        (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val =
          (op_193_cycle_isolated_vertex_chromatic_le_mmin
            (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩).val := by
      unfold op_193_cycle_isolated_vertex_chromatic_le_colorFin
      rw [dif_neg h]
    
  9. It suffices to show that colorFin assigns distinct colors to any adjacent vertices v and w.

    Linear arithmetic gives m - 2*k + 1 < m using k ≥ 3. Applying SimpleGraph.Colorable.chromaticNumber_le with SimpleGraph.Coloring.mk reduces the upper bound on the chromatic number to showing that adjacent vertices v and w (disjoint k-independent sets) receive different colors. We assume for contradiction that they receive the same color.

    lines 138–147

    uses SimpleGraph.Colorable.chromaticNumber_le, SimpleGraph.Coloring.mk

    theorem op_193_cycle_isolated_vertex_chromatic_le
        (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :
        (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber ≤
          m - 2 * k + 3 := by
      have hfb : m - 2*k + 1 < m := by omega
      apply SimpleGraph.Colorable.chromaticNumber_le
      refine ⟨SimpleGraph.Coloring.mk (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb) ?_⟩
      intro v w hadj
      have hdisj : Disjoint v.1 w.1 := hadj.1
      intro heq
  10. Adjacent vertices v and w cannot both contain the isolated vertex.

    Adjacent vertices in the Kneser graph are disjoint sets. If both contained the isolated vertex Sum.inr (), they would share an element, contradicting disjointness.

    lines 148–153

    uses Finset.disjoint_left

      have hvaleq : (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val =
          (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb w).val := by
        rw [heq]
      by_cases hv : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1
      · by_cases hw : (Sum.inr () : Fin m ⊕ Unit) ∈ w.1
        · exact (Finset.disjoint_left.mp hdisj hv) hw
  11. It is impossible for v to contain the isolated vertex while w does not. automation

    In this case, v has color m - 2*k + 2 while w has color at most m - 2*k + 1. Since these cannot be equal, this contradicts the assumption that their colors are the same.

    lines 154–160

    uses op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem, op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem, op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le

        · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem k m hfb v hv,
              op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb w hw] at hvaleq
          have hwle : (op_193_cycle_isolated_vertex_chromatic_le_mmin
              (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1)
              ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=
            op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le _ _
          omega
  12. Symmetrically, it is impossible for w to contain the isolated vertex while v does not. automation

    Here w has color m - 2*k + 2 and v has color at most m - 2*k + 1, which again contradicts the equality of their colors.

    lines 161–168

    uses op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem, op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem, op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le

      · by_cases hw : (Sum.inr () : Fin m ⊕ Unit) ∈ w.1
        · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb v hv,
              op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem k m hfb w hw] at hvaleq
          have hvle : (op_193_cycle_isolated_vertex_chromatic_le_mmin
              (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)
              ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=
            op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le _ _
          omega
  13. The case where neither v nor w contains the isolated vertex is impossible, concluding the proof.

    When neither contains the isolated vertex, both project to disjoint k-subsets of the cycle. By op_193_cycle_isolated_vertex_chromatic_le_core_min_ne, their cutoff minimums must be distinct, contradicting that their colors are equal.

    lines 169–185

    uses op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem, op_193_cycle_isolated_vertex_chromatic_le_card_inlPart, Finset.disjoint_left, op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart, op_193_cycle_isolated_vertex_chromatic_le_core_min_ne, Fin.ext

        · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb v hv,
              op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb w hw] at hvaleq
          have hAcard : (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1).card = k := by
            rw [op_193_cycle_isolated_vertex_chromatic_le_card_inlPart v.1 hv, v.2.card_eq]
          have hBcard : (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1).card = k := by
            rw [op_193_cycle_isolated_vertex_chromatic_le_card_inlPart w.1 hw, w.2.card_eq]
          have hAdisj : Disjoint (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)
              (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1) := by
            rw [Finset.disjoint_left]
            intro a ha hb
            rw [op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart] at ha hb
            exact (Finset.disjoint_left.mp hdisj ha) hb
          have hne := op_193_cycle_isolated_vertex_chromatic_le_core_min_ne
            (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)
            (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1)
            hAdisj hAcard hBcard ⟨m - 2*k + 1, hfb⟩ rfl
          exact hne (Fin.ext hvaleq)
Sum.inl_injective
The constructor Sum.inl is injective.
Finset.mem_preimage
An element is in the preimage of a set under f if and only if its image under f is in the set.
Finset.mem_map
An element is in the image of a set under an embedding if and only if it is the image of some element in the set.
Finset.card_map
The cardinality of the image of a finset under an embedding equals the cardinality of the original finset.
congrArg
Equal arguments produce equal results under any function.
op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem
Any element in a set is greater than or equal to the minimum of that set and a cutoff element.
Finset.card_union_of_disjoint
The cardinality of the union of disjoint finsets is the sum of their cardinalities.
Finset.union_subset
If two sets are subsets of a third, their union is also a subset of that third set.
Finset.card_le_card
If one set is a subset of another, its cardinality is at most the other set's cardinality.
Fin.card_Ici
The cardinality of the interval [a, n - 1] in Fin n is n - a.
Finset.mem_Ici
An element is in the upper interval Ici a if and only if it is at least a.
op_193_cycle_isolated_vertex_chromatic_le_mmin_mem
The minimum of A ∪ {fb} is an element of A ∪ {fb}.
Finset.mem_singleton
An element is in a singleton set {a} if and only if it equals a.
op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le
The minimum of A and fb is at most fb.
dif_pos
Under a true condition, a dependent if-then-else evaluates to the then-branch.
dif_neg
Under a false condition, a dependent if-then-else evaluates to the else-branch.
SimpleGraph.Colorable.chromaticNumber_le
A graph with an n-coloring has chromatic number at most n.
SimpleGraph.Coloring.mk
Constructs a graph coloring from a function assigning colors to vertices and a proof that adjacent vertices receive different colors.
Finset.disjoint_left
Two sets are disjoint if and only if no element in the first is in the second.
op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem
If the isolated vertex is in an independent set v, its color value is m - 2*k + 2.
op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem
If the isolated vertex is not in v, its color value is the minimum of its cycle elements and the cutoff fb.
op_193_cycle_isolated_vertex_chromatic_le_card_inlPart
If an independent set does not contain the isolated vertex, its cycle projection has the same cardinality.
op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart
An element is in the cycle projection of S if and only if its left-injection is in S.
op_193_cycle_isolated_vertex_chromatic_le_core_min_ne
For disjoint k-subsets A and B of a cycle, their cutoff minimums at m - 2*k + 1 are distinct.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.

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 Finsetnoncomputable def op_193_cycle_isolated_vertex_chromatic_le_inlPart {m : ℕ}    (S : Finset (Fin m ⊕ Unit)) : Finset (Fin m) :=  S.preimage Sum.inl (by    intro a ha b hb hab    exact Sum.inl_injective hab)lemma op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart {m : ℕ}    (S : Finset (Fin m ⊕ Unit)) (a : Fin m) :    a ∈ op_193_cycle_isolated_vertex_chromatic_le_inlPart S ↔ Sum.inl a ∈ S := by  unfold op_193_cycle_isolated_vertex_chromatic_le_inlPart  exact Finset.mem_preimagelemma op_193_cycle_isolated_vertex_chromatic_le_card_inlPart {m : ℕ}    (S : Finset (Fin m ⊕ Unit)) (h : (Sum.inr () : Fin m ⊕ Unit) ∉ S) :    (op_193_cycle_isolated_vertex_chromatic_le_inlPart S).card = S.card := by  have hmap :      (op_193_cycle_isolated_vertex_chromatic_le_inlPart S).map        ⟨Sum.inl, Sum.inl_injective⟩ = S := by    ext x    rw [Finset.mem_map]    constructor    · rintro ⟨a, ha, rfl⟩      exact (op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart S a).mp ha    · intro hx      rcases x with a | u      · exact ⟨a, (op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart S a).mpr hx, rfl⟩      · exact absurd hx (by simpa using h)  have hc := congrArg Finset.card hmap  rw [Finset.card_map] at hc  exact hcnoncomputable def op_193_cycle_isolated_vertex_chromatic_le_mmin {m : ℕ}    (A : Finset (Fin m)) (fb : Fin m) : Fin m :=  (A ∪ {fb}).min' ⟨fb, Finset.mem_union_right _ (Finset.mem_singleton_self fb)⟩lemma op_193_cycle_isolated_vertex_chromatic_le_mmin_mem {m : ℕ}    (A : Finset (Fin m)) (fb : Fin m) :    op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ∈ A ∪ {fb} :=  Finset.min'_mem _ _lemma op_193_cycle_isolated_vertex_chromatic_le_mmin_le {m : ℕ}    (A : Finset (Fin m)) (fb : Fin m) :    op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ≤ fb :=  Finset.min'_le _ _ (Finset.mem_union_right _ (Finset.mem_singleton_self fb))lemma op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem {m : ℕ}    {A : Finset (Fin m)} {fb : Fin m} {a : Fin m} (ha : a ∈ A) :    op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ≤ a :=  Finset.min'_le _ _ (Finset.mem_union_left _ ha)lemma op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le {m : ℕ}    (A : Finset (Fin m)) (fb : Fin m) :    (op_193_cycle_isolated_vertex_chromatic_le_mmin A fb).val ≤ fb.val :=  op_193_cycle_isolated_vertex_chromatic_le_mmin_le A fblemma op_193_cycle_isolated_vertex_chromatic_le_core_min_ne {m k : ℕ}    (A B : Finset (Fin m)) (hdisj : Disjoint A B) (hA : A.card = k) (hB : B.card = k)    (fb : Fin m) (hfbval : fb.val = m - 2*k + 1) :    op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ≠      op_193_cycle_isolated_vertex_chromatic_le_mmin B fb := by  intro heq  by_cases hAfb : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb = fb  · have hBfb : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb = fb := by      rw [← heq]; exact hAfb    have hAsub : A ⊆ Finset.Ici fb := by      intro a ha      rw [Finset.mem_Ici]      calc fb = op_193_cycle_isolated_vertex_chromatic_le_mmin A fb := hAfb.symm        _ ≤ a := op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem ha    have hBsub : B ⊆ Finset.Ici fb := by      intro a ha      rw [Finset.mem_Ici]      calc fb = op_193_cycle_isolated_vertex_chromatic_le_mmin B fb := hBfb.symm        _ ≤ a := op_193_cycle_isolated_vertex_chromatic_le_mmin_le_of_mem ha    have hunion : (A ∪ B).card = A.card + B.card := Finset.card_union_of_disjoint hdisj    have hunionsub : A ∪ B ⊆ Finset.Ici fb := Finset.union_subset hAsub hBsub    have hle : (A ∪ B).card ≤ (Finset.Ici fb).card := Finset.card_le_card hunionsub    rw [hunion, hA, hB, Fin.card_Ici, hfbval] at hle    omega  · have hBfb : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb ≠ fb := by      rw [← heq]; exact hAfb    have hA_mem : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ∈ A := by      have h := op_193_cycle_isolated_vertex_chromatic_le_mmin_mem A fb      rcases Finset.mem_union.mp h with h | h      · exact h      · rw [Finset.mem_singleton] at h        exact absurd h hAfb    have hB_mem : op_193_cycle_isolated_vertex_chromatic_le_mmin B fb ∈ B := by      have h := op_193_cycle_isolated_vertex_chromatic_le_mmin_mem B fb      rcases Finset.mem_union.mp h with h | h      · exact h      · rw [Finset.mem_singleton] at h        exact absurd h hBfb    have hnot : op_193_cycle_isolated_vertex_chromatic_le_mmin A fb ∉ B :=      Finset.disjoint_left.mp hdisj hA_mem    exact hnot (heq ▸ hB_mem)noncomputable def op_193_cycle_isolated_vertex_chromatic_le_colorFin (k m : ℕ)    (hfb : m - 2*k + 1 < m)    (v : { s : Finset (Fin m ⊕ Unit) //      ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s }) :    Fin (m - 2*k + 3) :=  if hin : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1 then    ⟨m - 2*k + 2, by omega⟩  else    ⟨(op_193_cycle_isolated_vertex_chromatic_le_mmin        (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩).val, by      have h1 : (op_193_cycle_isolated_vertex_chromatic_le_mmin          (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)          ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=        op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le          (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩      omega⟩lemma op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem (k m : ℕ)    (hfb : m - 2*k + 1 < m)    (v : { s : Finset (Fin m ⊕ Unit) //      ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s })    (h : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1) :    (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val = m - 2*k + 2 := by  unfold op_193_cycle_isolated_vertex_chromatic_le_colorFin  rw [dif_pos h]lemma op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem (k m : ℕ)    (hfb : m - 2*k + 1 < m)    (v : { s : Finset (Fin m ⊕ Unit) //      ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k s })    (h : (Sum.inr () : Fin m ⊕ Unit) ∉ v.1) :    (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val =      (op_193_cycle_isolated_vertex_chromatic_le_mmin        (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1) ⟨m - 2*k + 1, hfb⟩).val := by  unfold op_193_cycle_isolated_vertex_chromatic_le_colorFin  rw [dif_neg h]/-- General upper bound for OP-193: the chromatic number of KG(C_m ⊔ K_1, k) is at most m - 2k + 3. -/theorem op_193_cycle_isolated_vertex_chromatic_le    (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :    (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber ≤      m - 2 * k + 3 := by  have hfb : m - 2*k + 1 < m := by omega  apply SimpleGraph.Colorable.chromaticNumber_le  refine ⟨SimpleGraph.Coloring.mk (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb) ?_⟩  intro v w hadj  have hdisj : Disjoint v.1 w.1 := hadj.1  intro heq  have hvaleq : (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb v).val =      (op_193_cycle_isolated_vertex_chromatic_le_colorFin k m hfb w).val := by    rw [heq]  by_cases hv : (Sum.inr () : Fin m ⊕ Unit) ∈ v.1  · by_cases hw : (Sum.inr () : Fin m ⊕ Unit) ∈ w.1    · exact (Finset.disjoint_left.mp hdisj hv) hw    · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem k m hfb v hv,          op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb w hw] at hvaleq      have hwle : (op_193_cycle_isolated_vertex_chromatic_le_mmin          (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1)          ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=        op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le _ _      omega  · by_cases hw : (Sum.inr () : Fin m ⊕ Unit) ∈ w.1    · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb v hv,          op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_mem k m hfb w hw] at hvaleq      have hvle : (op_193_cycle_isolated_vertex_chromatic_le_mmin          (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)          ⟨m - 2*k + 1, hfb⟩).val ≤ m - 2*k + 1 :=        op_193_cycle_isolated_vertex_chromatic_le_mmin_val_le _ _      omega    · rw [op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb v hv,          op_193_cycle_isolated_vertex_chromatic_le_colorFin_val_of_not_mem k m hfb w hw] at hvaleq      have hAcard : (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1).card = k := by        rw [op_193_cycle_isolated_vertex_chromatic_le_card_inlPart v.1 hv, v.2.card_eq]      have hBcard : (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1).card = k := by        rw [op_193_cycle_isolated_vertex_chromatic_le_card_inlPart w.1 hw, w.2.card_eq]      have hAdisj : Disjoint (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)          (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1) := by        rw [Finset.disjoint_left]        intro a ha hb        rw [op_193_cycle_isolated_vertex_chromatic_le_mem_inlPart] at ha hb        exact (Finset.disjoint_left.mp hdisj ha) hb      have hne := op_193_cycle_isolated_vertex_chromatic_le_core_min_ne        (op_193_cycle_isolated_vertex_chromatic_le_inlPart v.1)        (op_193_cycle_isolated_vertex_chromatic_le_inlPart w.1)        hAdisj hAcard hBcard ⟨m - 2*k + 1, hfb⟩ rfl      exact hne (Fin.ext hvaleq)
See it in the graphDiscuss this resultChallenge it