op_193_cubic_tight_if_cycle_lower
For k at least 3 and m at least k((k-1)²+1), the stable k-set graph of the m-cycle plus an isolated vertex has chromatic number m-2k+3, provided the cycle-only stable k-set graph has chromatic number at least m-2k+2.
Statement
theorem op_193_cubic_tight_if_cycle_lower (k m : ℕ) (hk : 3 ≤ k)
(hm : k * ((k-1)^2+1) ≤ m)
(hcycle : ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber) :
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
m-2*k+3- Source
- Explicit-threshold refinement of arXiv:2610.17884 Section 3.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- op_193_cubic_noncolorable_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), if the cycle-stable k-set graph is not (m-2k+1)-colorable, then adding an isolated vertex…
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof establishes that the chromatic number of the stable k-set graph of the m-cycle plus an isolated vertex is m - 2k + 3 by proving the lower bound m - 2k + 3 ≤ χ and applying an equivalence lemma (op_193_cycle_isolated_vertex_k_tight_iff_ge) that equates this lower bound with exactness. The lower bound on the cycle's chromatic number first implies that the cycle's stable graph is not (m - 2k + 1)-colorable. By a known transfer theorem (op_193_cubic_noncolorable_if_cycle_lower), adding an isolated vertex raises the uncolorability threshold to m - 2k + 2, forcing the chromatic number to be strictly greater than m - 2k + 2, and therefore at least m - 2k + 3.
4 ≤ (k - 1)² + 1
Since k ≥ 3, we have k - 1 ≥ 2. Squaring gives (k - 1)² ≥ 4, so (k - 1)² + 1 ≥ 5 ≥ 4.
have hf : 4 ≤ (k-1)^2+1 := by have hh : 2 ≤ k-1 := by omega nlinarith
4k - 3 ≤ m
Multiplying the inequality 4 ≤ (k - 1)² + 1 by k yields 4k ≤ k((k - 1)² + 1). Combined with the hypothesis m ≥ k((k - 1)² + 1), linear arithmetic gives 4k - 3 ≤ m.
uses
Nat.mul_le_mul_lefthave hm4 : 4*k-3 ≤ m := by have hh := Nat.mul_le_mul_left k hf omega
The stable k-set graph of the m-cycle is not (m - 2k + 1)-colorable.
Suppose it were (m - 2k + 1)-colorable. Then its chromatic number would be at most m - 2k + 1. But the hypothesis states that its chromatic number is at least m - 2k + 2. Since m - 2k + 1 < m - 2k + 2, this produces a contradiction via not_le_of_gt.
uses
not_le_of_gthave hnotcycle : ¬ (GStableKneser (SimpleGraph.cycleGraph m) k).Colorable (m-2*k+1) := by intro hc have hu := hc.chromaticNumber_le have hlt : ((m-2*k+1 : ℕ) : ℕ∞) < ((m-2*k+2 : ℕ) : ℕ∞) := by exact_mod_cast (by omega : m-2*k+1 < m-2*k+2) exact (not_le_of_gt hlt) (hcycle.trans hu)
The stable k-set graph of the m-cycle plus an isolated vertex is not (m - 2k + 2)-colorable.
Applying the transfer lemma op_193_cubic_noncolorable_if_cycle_lower to the parameters k and m and the non-colorability of the cycle stable graph shows that adding an isolated vertex yields a graph that cannot be colored with m - 2k + 2 colors.
uses
op_193_cubic_noncolorable_if_cycle_lowerhave hnot := op_193_cubic_noncolorable_if_cycle_lower k m hk hm hnotcycleThe chromatic number of the stable k-set graph of the m-cycle plus an isolated vertex is strictly greater than m - 2k + 2.
By lt_of_not_ge, it suffices to rule out that the chromatic number is at most m - 2k + 2. If it were, SimpleGraph.chromaticNumber_le_iff_colorable would imply it is (m - 2k + 2)-colorable, contradicting the previous step.
uses
lt_of_not_ge,SimpleGraph.chromaticNumber_le_iff_colorablehave hlt : ((m-2*k+2 : ℕ) : ℕ∞) < (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := by apply lt_of_not_ge intro h exact hnot ((SimpleGraph.chromaticNumber_le_iff_colorable (n := m-2*k+2)).mp h)
The chromatic number of the stable k-set graph of the m-cycle plus an isolated vertex is at least m - 2k + 3, as a cast natural number.
In the extended natural numbers, a strict inequality n < χ implies n + 1 ≤ χ by ENat.natCast_add_one_le_iff.mpr. Taking n = m - 2k + 2 yields (m - 2k + 2) + 1 ≤ χ, and arithmetic simplifies the left-hand side to m - 2k + 3.
uses
ENat.natCast_add_one_le_iff.mprhave hge : (((m-2*k+2)+1 : ℕ) : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := ENat.natCast_add_one_le_iff.mpr hlt have hn : (m-2*k+2)+1 = m-2*k+3 := by omega rw [hn] at hge
The lower bound m - 2k + 3 ≤ χ holds for the algebraic expression in ℕ∞.
Coercions from ℕ to ℕ∞ distribute over addition, subtraction, and multiplication via ENat.natCast_add, ENat.natCast_sub, and ENat.natCast_mul. Rewriting with these rules aligns the coerced natural number with the ℕ∞ arithmetic expression in the goal.
uses
ENat.natCast_add,ENat.natCast_sub,ENat.natCast_mulhave hN : ((m-2*k+3 : ℕ) : ℕ∞) = (m : ℕ∞)-2*(k : ℕ∞)+3 := by rw [ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul] norm_num rw [hN] at hge
The chromatic number of the stable k-set graph of the m-cycle plus an isolated vertex is exactly m - 2k + 3.
Lemma op_193_cycle_isolated_vertex_k_tight_iff_ge shows that for k ≥ 3 and 4k - 3 ≤ m, the chromatic number equals m - 2k + 3 if and only if it is at least m - 2k + 3. Since the lower bound was established, equality follows.
uses
op_193_cycle_isolated_vertex_k_tight_iff_geexact (op_193_cycle_isolated_vertex_k_tight_iff_ge k m hk hm4).mpr hge
Nat.mul_le_mul_left- For natural numbers n, m and k, if n ≤ m, then k * n ≤ k * m.
not_le_of_gt- In a preorder, if a < b, then it is not the case that b ≤ a.
op_193_cubic_noncolorable_if_cycle_lower- For k ≥ 3 and m ≥ k((k-1)²+1), if the stable k-set graph of the m-cycle is not (m-2k+1)-colorable, then adding an isolated vertex produces a graph that is not (m-2k+2)-colorable.
lt_of_not_ge- In a linear order, if not b ≤ a, then a < b.
SimpleGraph.chromaticNumber_le_iff_colorable- A simple graph has chromatic number at most n if and only if it is n-colorable.
ENat.natCast_add_one_le_iff.mpr- For a natural number m and an extended natural x, if m < x, then m + 1 ≤ x.
ENat.natCast_add- The coercion from ℕ to ℕ∞ preserves addition: ↑(m + n) = ↑m + ↑n.
ENat.natCast_sub- The coercion from ℕ to ℕ∞ preserves subtraction: ↑(m - n) = ↑m - ↑n.
ENat.natCast_mul- The coercion from ℕ to ℕ∞ preserves multiplication: ↑(m * n) = ↑m * ↑n.
op_193_cycle_isolated_vertex_k_tight_iff_ge- For k ≥ 3 and 4k - 3 ≤ m, the stable k-set graph of the m-cycle plus an isolated vertex has chromatic number equal to m - 2k + 3 if and only if its chromatic number is at least m - 2k + 3.
- Chromatic numbers in Lean are valued in the extended natural numbers ℕ∞ (ℕ with +∞), requiring explicit cast lemmas when translating between ℕ and ℕ∞ arithmetic.
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.
theorem op_193_cubic_tight_if_cycle_lower (k m : ℕ) (hk : 3 ≤ k) (hm : k * ((k-1)^2+1) ≤ m) (hcycle : ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber) : (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber = m-2*k+3 := by have hf : 4 ≤ (k-1)^2+1 := by have hh : 2 ≤ k-1 := by omega nlinarith have hm4 : 4*k-3 ≤ m := by have hh := Nat.mul_le_mul_left k hf omega have hnotcycle : ¬ (GStableKneser (SimpleGraph.cycleGraph m) k).Colorable (m-2*k+1) := by intro hc have hu := hc.chromaticNumber_le have hlt : ((m-2*k+1 : ℕ) : ℕ∞) < ((m-2*k+2 : ℕ) : ℕ∞) := by exact_mod_cast (by omega : m-2*k+1 < m-2*k+2) exact (not_le_of_gt hlt) (hcycle.trans hu) have hnot := op_193_cubic_noncolorable_if_cycle_lower k m hk hm hnotcycle have hlt : ((m-2*k+2 : ℕ) : ℕ∞) < (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := by apply lt_of_not_ge intro h exact hnot ((SimpleGraph.chromaticNumber_le_iff_colorable (n := m-2*k+2)).mp h) have hge : (((m-2*k+2)+1 : ℕ) : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := ENat.natCast_add_one_le_iff.mpr hlt have hn : (m-2*k+2)+1 = m-2*k+3 := by omega rw [hn] at hge have hN : ((m-2*k+3 : ℕ) : ℕ∞) = (m : ℕ∞)-2*(k : ℕ∞)+3 := by rw [ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul] norm_num rw [hN] at hge exact (op_193_cycle_isolated_vertex_k_tight_iff_ge k m hk hm4).mpr hge