op_193_cycle_isolated_vertex_chromatic_ge_cycle
For any natural numbers k and m, the chromatic number of the G-stable Kneser graph of the disjoint union of an m-cycle and an isolated vertex is at least the chromatic number of the G-stable Kneser graph of the m-cycle.
Statement
theorem op_193_cycle_isolated_vertex_chromatic_ge_cycle (k m : ℕ) :
(GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber ≤
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber- Source
- arXiv:2610.17884 Sec. 1 -- 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_kneser_hom_sum_inlFor any simple graphs G and H and any natural number k, there exists a graph homomorphism from the G-stable Kneser graph KG(G, k) to the…
Read back from the Lean
For all natural numbers $k$ and $m$, the chromatic number of the $G$-stable Kneser graph of parameter $k$ on the cycle graph on $m$ vertices (SimpleGraph.cycleGraph m) is less than or equal to the chromatic number of the $G$-stable Kneser graph of parameter $k$ on the graph obtained by taking the disjoint union of SimpleGraph.cycleGraph m and an isolated vertex (the bottom/edgeless graph on Unit).
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 inequality is established by exhibiting a graph homomorphism and applying the monotonicity of chromatic numbers. Specifically, embedding the cycle graph C_m into the disjoint union C_m ⊔ K_1 induces a graph homomorphism between their corresponding G-stable Kneser graphs, which immediately implies that the chromatic number of the latter is at least that of the former.
There exists a graph homomorphism from the G-stable Kneser graph of C_m to that of C_m ⊔ K_1.
By `op_193_kneser_hom_sum_inl`, the inclusion of any graph G into a disjoint union G ⊕ H induces a graph homomorphism between their respective G-stable Kneser graphs. We apply this to G = C_m (the cycle graph on m vertices) and H = K_1 (an isolated vertex, represented by the empty graph on Unit) to obtain such a homomorphism f.
uses
op_193_kneser_hom_sum_inlobtain ⟨f⟩ := op_193_kneser_hom_sum_inl (SimpleGraph.cycleGraph m) (⊥ : SimpleGraph Unit) kThe chromatic number of KG(C_m, k) is at most the chromatic number of KG(C_m ⊔ K_1, k).
Since graph homomorphisms are chromatic-number-nonincreasing (or equivalently, target chromatic numbers bound domain chromatic numbers from above), the existence of the homomorphism f from KG(C_m, k) to KG(C_m ⊔ K_1, k) proves the inequality.
uses
SimpleGraph.chromaticNumber_mono_of_homexact SimpleGraph.chromaticNumber_mono_of_hom f
op_193_kneser_hom_sum_inl- For any graphs G and H and any natural number k, there exists a graph homomorphism from the G-stable Kneser graph of G to the G-stable Kneser graph of the disjoint union G ⊕ H.
SimpleGraph.chromaticNumber_mono_of_hom- If there exists 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 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 chromatic number of KG(C_m ⊔ K_1, k) is at least the chromatic number of KG(C_m, k). -/theorem op_193_cycle_isolated_vertex_chromatic_ge_cycle (k m : ℕ) : (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := by obtain ⟨f⟩ := op_193_kneser_hom_sum_inl (SimpleGraph.cycleGraph m) (⊥ : SimpleGraph Unit) k exact SimpleGraph.chromaticNumber_mono_of_hom f