AFTD Auto-Formalizing Theoretical Domains

op_193_cycle_isolated_vertex_k_tight_iff_ge

theoremverified

For 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 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3.

Statement

theorem op_193_cycle_isolated_vertex_k_tight_iff_ge
    (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :
    (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
      m - 2 * k + 3 ↔
    (m - 2 * k + 3 : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber
Source
arXiv:2610.17884 Sec. 1 -- The chromatic number of G-stable Kneser graphs
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • op_193_cycle_isolated_vertex_chromatic_leFor 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…
  • 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…
Used by 1
  • op_193_cubic_tight_if_cycle_lowerFor 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,…

Read back from the Lean

For any natural numbers $k$ and $m$ satisfying $k \ge 3$ and $m \ge 4k - 3$, the chromatic number of the generalized (stable) Kneser graph on the $k$-element independent sets of the disjoint union of the $m$-cycle graph and an isolated vertex (the edgeless graph on Unit) is equal to $m - 2k + 3$ if and only if its chromatic number is at least $m - 2k + 3$ (in $\mathbb{N}_\infty$).

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

The theorem states that for k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3. The forward direction is trivial by reflexivity of the order. The reverse direction combines the assumed lower bound with the established upper bound from `op_193_cycle_isolated_vertex_chromatic_le` using antisymmetry of ≤.

  1. The natural arithmetic expression m - 2*k + 3 coerced to ℕ∞ equals the expression evaluated in ℕ∞.

    Distribute the coercion from ℕ to ℕ∞ across the addition, subtraction, and multiplication using `ENat.natCast_add`, `ENat.natCast_sub`, and `ENat.natCast_mul`, and simplify the numerals with `norm_num`.

    lines 7–9

    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
  2. The equivalence reduces to proving each implication separately.

    Split the if-and-only-if goal into the forward direction (equality implies the inequality) and the reverse direction (the inequality implies equality).

    line 10

      constructor
  3. If the chromatic number equals m - 2*k + 3, then it is at least m - 2*k + 3.

    Assume the chromatic number equals m - 2*k + 3. Rewriting by this assumption reduces the goal to reflexivity of ≤.

    lines 11–12

      · intro h
        rw [h]
  4. If the chromatic number is at least m - 2*k + 3, then it equals m - 2*k + 3.

    Assume the lower bound h. The matching upper bound that the chromatic number is at most m - 2*k + 3 is given by `op_193_cycle_isolated_vertex_chromatic_le` (adjusted by `hN`). Combining the two inequalities via `le_antisymm` yields equality.

    lines 13–15

    uses le_antisymm, op_193_cycle_isolated_vertex_chromatic_le

      · intro h
        exact le_antisymm
          (by simpa [hN] using op_193_cycle_isolated_vertex_chromatic_le k m hk hm) h
ENat.natCast_add
The natural cast into ℕ∞ distributes over addition: ↑(m + n) = ↑m + ↑n.
ENat.natCast_sub
The natural cast into ℕ∞ distributes over subtraction: ↑(m - n) = ↑m - ↑n.
ENat.natCast_mul
The natural cast into ℕ∞ distributes over multiplication: ↑(m * n) = ↑m * ↑n.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
op_193_cycle_isolated_vertex_chromatic_le
For k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 is at most m - 2*k + 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

/-- The chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3. -/theorem op_193_cycle_isolated_vertex_k_tight_iff_ge    (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :    (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =      m - 2 * k + 3 ↔    (m - 2 * k + 3 : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := by  have hN : ((m - 2 * k + 3 : ℕ) : ℕ∞) = (m : ℕ∞) - 2 * (k : ℕ∞) + 3 := by    rw [ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul]    norm_num  constructor  · intro h    rw [h]  · intro h    exact le_antisymm      (by simpa [hN] using op_193_cycle_isolated_vertex_chromatic_le k m hk hm) h
See it in the graphDiscuss this resultChallenge it