AFTD Auto-Formalizing Theoretical Domains

not_is_k_tight_empty

theoremverified

The empty graph on 0 vertices is not k-tight for any k ≥ 2.

Statement

lemma not_is_k_tight_empty (k : ℕ) (hk : 2 ≤ k) :
    ¬ is_k_tight (⊥ : SimpleGraph Empty) k
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 every natural number $k$ such that $2 \le k$, the empty (edgeless) graph $\bot$ on the empty type Empty is not $k$-tight.

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

To show that the empty graph on 0 vertices is not k-tight for k ≥ 2, we compare the chromatic number of its stable Kneser graph with the formula |Empty| - 2 * k + 2. Because no subset of the empty set has size k ≥ 2, the stable Kneser graph has no vertices and its chromatic number is 0. Meanwhile, truncated natural number arithmetic yields |Empty| - 2 * k + 2 = 0 - 2 * k + 2 = 2. Since 0 ≠ 2, the empty graph is not k-tight.

  1. The chromatic number of the stable Kneser graph on the empty graph is 0.

    Unfolding the definition of k-tightness, we must show that the chromatic number of the stable Kneser graph GStableKneser ⊥ k does not equal |Empty| - 2 * k + 2. The vertices of the stable Kneser graph are the independent sets of size k in the empty graph. Any subset s of the empty type Empty contains no elements, so s = ∅, which implies its cardinality is 0 by Finset.card_eq_zero. On the other hand, an independent set of size k must have cardinality k. Since k ≥ 2, no such subset can exist, making the vertex type empty (IsEmpty). Rewriting with SimpleGraph.chromaticNumber_eq_zero_of_isEmpty then shows that the chromatic number of the graph is 0.

    lines 4–14

    uses Finset.card_eq_zero, SimpleGraph.chromaticNumber_eq_zero_of_isEmpty

      unfold is_k_tight
      haveI : IsEmpty { s : Finset Empty // (⊥ : SimpleGraph Empty).IsNIndepSet k s } := by
        constructor
        rintro ⟨s, hs⟩
        have hcard : s.card = k := hs.card_eq
        have hz : s.card = 0 := by
          rw [Finset.card_eq_zero]
          ext x
          exact x.elim
        omega
      rw [SimpleGraph.chromaticNumber_eq_zero_of_isEmpty]
  2. The target value |Empty| - 2 * k + 2 evaluates to 2.

    The cardinality of Empty is 0. Under truncated subtraction on the natural numbers (ℕ), 0 - 2 * k = 0 for any k, and therefore 0 - 2 * k + 2 = 2.

    lines 15–17

      have hrhs : Fintype.card Empty - 2 * k + 2 = 2 := by
        have h0 : Fintype.card Empty = 0 := by simp
        omega
  3. The empty graph is not k-tight.

    Substituting the computed value of the right-hand side reduces the condition to 0 ≠ 2, which holds immediately.

    lines 18–19

      rw [hrhs]
      simp
Finset.card_eq_zero
A finite set has cardinality 0 if and only if it is empty.
SimpleGraph.chromaticNumber_eq_zero_of_isEmpty
A simple graph on an empty vertex type has chromatic number 0.

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 empty graph on 0 vertices is not k-tight for any k ≥ 2. -/lemma not_is_k_tight_empty (k : ℕ) (hk : 2 ≤ k) :    ¬ is_k_tight (⊥ : SimpleGraph Empty) k := by  unfold is_k_tight  haveI : IsEmpty { s : Finset Empty // (⊥ : SimpleGraph Empty).IsNIndepSet k s } := by    constructor    rintro ⟨s, hs⟩    have hcard : s.card = k := hs.card_eq    have hz : s.card = 0 := by      rw [Finset.card_eq_zero]      ext x      exact x.elim    omega  rw [SimpleGraph.chromaticNumber_eq_zero_of_isEmpty]  have hrhs : Fintype.card Empty - 2 * k + 2 = 2 := by    have h0 : Fintype.card Empty = 0 := by simp    omega  rw [hrhs]  simp
See it in the graphDiscuss this resultChallenge it