op_193_cycle_isolated_vertex_chromatic_le
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 3
- op_193_cycle_isolated_vertex_k3_m10The stable triple graph of the ten-cycle plus an isolated vertex has chromatic number seven.
- op_193_cycle_isolated_vertex_k_tight_iff_geFor 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…
- op_193_cycle_isolated_vertex_k3_m9The G-stable Kneser graph KG(C_9 ⊔ K_1, 3), where the base graph is the disjoint sum of the 9-cycle and an isolated vertex, has chromatic…
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.
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.
uses
Sum.inl_injectiveS.preimage Sum.inl (by intro a ha b hb hab exact Sum.inl_injective hab)
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.
uses
Finset.mem_preimagelemma 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
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.
uses
Sum.inl_injective,Finset.mem_map,congrArg,Finset.card_maplemma 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
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.
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_Iciintro 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
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.
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)
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.
uses
op_193_cycle_isolated_vertex_chromatic_le_mmin_val_lenoncomputable 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⟩
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.
uses
dif_poslemma 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]
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.
uses
dif_neglemma 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]
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.
uses
SimpleGraph.Colorable.chromaticNumber_le,SimpleGraph.Coloring.mktheorem 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
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.
uses
Finset.disjoint_lefthave 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
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.
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
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.
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
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.
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
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 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)