not_is_k_tight_empty
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.
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.
uses
Finset.card_eq_zero,SimpleGraph.chromaticNumber_eq_zero_of_isEmptyunfold 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]
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.
have hrhs : Fintype.card Empty - 2 * k + 2 = 2 := by have h0 : Fintype.card Empty = 0 := by simp omega
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.
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.
- The evaluation of |Empty| - 2 * k + 2 relies on truncated natural number subtraction: because 0 - 2 * k = 0 in ℕ, the expression 0 - 2 * k + 2 evaluates to 2 rather than a negative integer.
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 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