AFTD Auto-Formalizing Theoretical Domains

is_k_tight_cycle_sum_unit_iff

theoremverified

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 ℕ∞.

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

    line 6

      have h2k : 2 * k ≤ m := by omega
  2. 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.

    lines 7–8

    uses is_k_tight, Fintype.card_sum, Fintype.card_fin, Fintype.card_unit

      rw [is_k_tight]
      simp only [Fintype.card_sum, Fintype.card_fin, Fintype.card_unit]
  3. 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.

    lines 9–10

      have harith : (m + 1) - 2 * k + 2 = m - 2 * k + 3 := by omega
      rw [harith]
  4. 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.

    lines 11–14

      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

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