is_k_tight_cycle_sum_unit_iff
For k ≥ 3 and m ≥ 4*k - 3, the disjoint sum of the m-cycle and an isolated vertex is k-tight if and only if the chromatic number of its G-stable Kneser graph equals m - 2*k + 3.
Statement
theorem is_k_tight_cycle_sum_unit_iff (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :
is_k_tight ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k ↔
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
m - 2 * k + 3- 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
- is_k_tightA finite graph G on n vertices is k-tight if the chromatic number of its G-stable Kneser graph KG(G, k) equals n - 2*k + 2.
- 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…
Read back from the Lean
For all natural numbers $k$ and $m$ satisfying $3 \le k$ and $4k - 3 \le m$: the graph formed by the disjoint union of the cycle graph $C_m$ (on vertex type ZMod m) and the empty graph on a single vertex (on vertex type Unit) is $k$-tight if and only if the chromatic number of its stable Kneser graph with parameter $k$ equals $m - 2k + 3$ (as an extended natural number in ℕ∞).
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 characterizes when the disjoint sum of an m-cycle and an isolated vertex is k-tight. By definition, k-tightness means the chromatic number of the G-stable Kneser graph equals |V| - 2*k + 2 in ℕ∞, where |V| = m + 1 is the vertex count of the disjoint sum. The proof simplifies the natural number arithmetic (m + 1) - 2*k + 2 to m - 2*k + 3 and uses the bound 2*k ≤ m to commute the subtraction with the coercion into ℕ∞.
2 * k ≤ m
From the assumptions k ≥ 3 and m ≥ 4*k - 3, we have m - 2*k ≥ 2*k - 3 ≥ 3 > 0, so 2*k ≤ m. Linear integer arithmetic (`omega`) establishes this inequality.
have h2k : 2 * k ≤ m := by omega
The condition that the graph is k-tight reduces to its G-stable Kneser chromatic number being (m + 1) - 2*k + 2 (cast to ℕ∞)
Unfolding the definition of `is_k_tight`, a graph on vertex set V is k-tight if the chromatic number of its G-stable Kneser graph is |V| - 2*k + 2 (as an element of ℕ∞). The vertex set of the disjoint sum is Fin m ⊕ Unit. Evaluating its cardinality using `Fintype.card_sum`, `Fintype.card_fin`, and `Fintype.card_unit` simplifies |V| to m + 1.
uses
is_k_tight,Fintype.card_sum,Fintype.card_fin,Fintype.card_unitrw [is_k_tight] simp only [Fintype.card_sum, Fintype.card_fin, Fintype.card_unit]
In ℕ, (m + 1) - 2*k + 2 = m - 2*k + 3
Because 2*k ≤ m, the natural number subtraction does not underflow to zero, so (m + 1) - 2*k + 2 = m - 2*k + 3. This arithmetic identity is verified by `omega` and then rewritten into the goal.
have harith : (m + 1) - 2 * k + 2 = m - 2 * k + 3 := by omega rw [harith]
The coerced natural number ↑(m - 2*k + 3) equals ↑m - 2*↑k + 3 in ℕ∞, completing the equivalence
We show that the coercion ↑(m - 2*k + 3) : ℕ∞ equals ↑m - 2*↑k + 3. Because 2*k ≤ m (by `h2k`), pushing the coercion across subtraction via `push_cast` is valid, and the ring structure of ℕ∞ (`ring`) simplifies the expression. Rewriting with this identity makes both sides of the iff statement identical, which finishes the proof.
have hcast : (↑(m - 2 * k + 3) : ℕ∞) = ↑m - 2 * ↑k + 3 := by push_cast [h2k] ring rw [hcast]
is_k_tight- a graph G on a finite vertex set V is k-tight if the chromatic number of its G-stable Kneser graph equals (Fintype.card V - 2 * k + 2 : ℕ∞)
Fintype.card_sum- the cardinality of the disjoint sum of two finite types is the sum of their cardinalities: |α ⊕ β| = |α| + |β|
Fintype.card_fin- the type Fin n has cardinality n: |Fin n| = n
Fintype.card_unit- the singleton type Unit has cardinality 1: |Unit| = 1
- In Lean, chromatic numbers take values in ℕ∞ (the extended natural numbers). In the definition of `is_k_tight`, the arithmetic |V| - 2*k + 2 is performed in ℕ before being coerced to ℕ∞, whereas the theorem statement performs subtraction directly in ℕ∞. The intermediate step `hcast` bridges this formal distinction, relying on 2*k ≤ m to guarantee that natural subtraction coincides with subtraction in ℕ∞.
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.
/-- The disjoint sum of an m-cycle and an isolated vertex is k-tight if and only if the chromatic number of its G-stable Kneser graph is m - 2*k + 3. -/theorem is_k_tight_cycle_sum_unit_iff (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) : is_k_tight ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k ↔ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber = m - 2 * k + 3 := by have h2k : 2 * k ≤ m := by omega rw [is_k_tight] simp only [Fintype.card_sum, Fintype.card_fin, Fintype.card_unit] have harith : (m + 1) - 2 * k + 2 = m - 2 * k + 3 := by omega rw [harith] have hcast : (↑(m - 2 * k + 3) : ℕ∞) = ↑m - 2 * ↑k + 3 := by push_cast [h2k] ring rw [hcast]