AFTD Auto-Formalizing Theoretical Domains

op_193_cycle_isolated_vertex_chromatic_ge_cycle

theoremverified

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.

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

    line 5

    uses op_193_kneser_hom_sum_inl

      obtain ⟨f⟩ := op_193_kneser_hom_sum_inl (SimpleGraph.cycleGraph m) (⊥ : SimpleGraph Unit) k
  2. The 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.

    line 6

    uses SimpleGraph.chromaticNumber_mono_of_hom

      exact 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

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