AFTD Auto-Formalizing Theoretical Domains

op_193_chromaticNumber_le_cycle_step

theoremverifiedformalization

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.

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

    line 5

    uses Nonempty.elim, op_193_hom_cycle_step, SimpleGraph.chromaticNumber_mono_of_hom

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