op_193_chromaticNumber_le_cycle_step
For all integers k ≥ 2 and r ≥ 2 * k - 2, the chromatic number of the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) is at most the chromatic number of the G-stable Kneser graph KG(C_r ⊔ K_1, k-1).
Statement
theorem op_193_chromaticNumber_le_cycle_step (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) :
(GStableKneser ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber ≤
(GStableKneser ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)) (k - 1)).chromaticNumber- Formalizes
- arXiv:2610.17884 Lemma 2.12 -- The chromatic number of G-stable Kneser graphs
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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…
- op_193_hom_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the…
Read back from the Lean
For any natural numbers $k$ and $r$ such that $2 \le k$ and $2k - 2 \le r$, the chromatic number of the generalized Kneser graph of $k$-element independent sets of the disjoint union of the cycle graph $C_{r+2}$ (on vertex type ZMod (r + 2)) and an isolated vertex (the empty graph on Unit) is less than or equal to the chromatic number of the generalized Kneser graph of $(k - 1)$-element independent sets of the disjoint union of the cycle graph $C_r$ (on vertex type ZMod r) and an isolated vertex.
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 proof relies on the standard fact that graph homomorphisms do not increase the chromatic number. Given k ≥ 2 and r ≥ 2k - 2, a previously established result (op_193_hom_cycle_step) guarantees that the collection of homomorphisms from KG(C_{r+2} ⊔ K_1, k) to KG(C_r ⊔ K_1, k-1) is nonempty. Applying monotonicity of chromatic numbers with respect to graph homomorphisms yields the inequality in a single step.
The chromatic number of KG(C_{r+2} ⊔ K_1, k) is at most the chromatic number of KG(C_r ⊔ K_1, k-1).
The theorem op_193_hom_cycle_step provides the existence of a graph homomorphism from KG(C_{r+2} ⊔ K_1, k) to KG(C_r ⊔ K_1, k-1). By SimpleGraph.chromaticNumber_mono_of_hom, any graph homomorphism f : G →g G' implies chromaticNumber G ≤ chromaticNumber G'. Eliminating the existential witness of the homomorphism via Nonempty.elim immediately yields the desired inequality.
uses
Nonempty.elim,op_193_hom_cycle_step,SimpleGraph.chromaticNumber_mono_of_homNonempty.elim (op_193_hom_cycle_step k r hk hr) SimpleGraph.chromaticNumber_mono_of_hom
Nonempty.elim- Given a proof that a type is nonempty, any proposition that follows from an arbitrary element of that type holds.
op_193_hom_cycle_step- For k ≥ 2 and r ≥ 2k - 2, there exists a graph homomorphism from KG(C_{r+2} ⊔ K_1, k) to KG(C_r ⊔ K_1, k-1).
SimpleGraph.chromaticNumber_mono_of_hom- If there is a graph homomorphism from G to G', then the chromatic number of G is at most the chromatic number of G'.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Monotonicity step: the chromatic number of KG(C_{r+2} ⊔ K_1, k) is at most that of KG(C_r ⊔ K_1, k-1). -/theorem op_193_chromaticNumber_le_cycle_step (k r : ℕ) (hk : 2 ≤ k) (hr : 2 * k - 2 ≤ r) : (GStableKneser ((SimpleGraph.cycleGraph (r + 2)).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber ≤ (GStableKneser ((SimpleGraph.cycleGraph r).sum (⊥ : SimpleGraph Unit)) (k - 1)).chromaticNumber := Nonempty.elim (op_193_hom_cycle_step k r hk hr) SimpleGraph.chromaticNumber_mono_of_hom