AFTD Auto-Formalizing Theoretical Domains

op_193_cubic_tight_if_cycle_lower

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 4 ≤ (k - 1)² + 1

    Since k ≥ 3, we have k - 1 ≥ 2. Squaring gives (k - 1)² ≥ 4, so (k - 1)² + 1 ≥ 5 ≥ 4.

    lines 6–8

      have hf : 4 ≤ (k-1)^2+1 := by
        have hh : 2 ≤ k-1 := by omega
        nlinarith
  2. 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.

    lines 9–11

    uses Nat.mul_le_mul_left

      have hm4 : 4*k-3 ≤ m := by
        have hh := Nat.mul_le_mul_left k hf
        omega
  3. 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.

    lines 12–17

    uses not_le_of_gt

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

    line 18

    uses op_193_cubic_noncolorable_if_cycle_lower

      have hnot := op_193_cubic_noncolorable_if_cycle_lower k m hk hm hnotcycle
  5. The 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.

    lines 19–23

    uses lt_of_not_ge, SimpleGraph.chromaticNumber_le_iff_colorable

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

    lines 24–28

    uses ENat.natCast_add_one_le_iff.mpr

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

    lines 29–32

    uses ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul

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

    line 33

    uses op_193_cycle_isolated_vertex_k_tight_iff_ge

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

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

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