simple_graph_k_independence_number_eq_card_of_degree_lt
If every vertex of the finite graph G has degree less than k, then β_k(G) = SF_k(G) = |V(G)|.
Statement
theorem simple_graph_k_independence_number_eq_card_of_degree_lt {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ v, G.degree v < k) : simple_graph_k_independence_number G k = Fintype.card V ∧ simple_graph_upper_k_star_forming_number G k = Fintype.card V
- Formalizes
- arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Proposition 3.1.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_k_independence_numberβ_k(G): the maximum cardinality of a k-independent vertex set of G.
- simple_graph_upper_k_star_forming_numberSF_k(G): the maximum cardinality of a minimal k-star-forming vertex set of G.
- simple_graph_is_minimal_k_star_formingA minimal k-star-forming set: a k-star-forming set no proper subset of which is k-star-forming.
- simple_graph_is_k_star_forming_univIn a finite graph the whole vertex set is k-star-forming, for every k (there is no vertex outside it).
- simple_graph_is_k_star_formingA vertex set S is k-star-forming when, for every vertex v outside S, the induced graph G[S ∪ {v}] contains a copy of the star K_{1,k} that…
- simple_graph_is_k_independentA vertex set I of a graph G is k-independent when the induced subgraph G[I] has maximum degree less than k: every vertex of I has fewer…
The proof, explained
Assuming every vertex of G has degree strictly less than k, the entire vertex set V is k-independent because no vertex has k or more neighbors. Furthermore, V is vacuously k-star-forming, whereas no proper subset of V can be k-star-forming because forming a k-star would require a center of degree at least k; hence V is minimal k-star-forming. Since no subset can exceed |V|, the suprema defining the k-independence number β_k(G) and the upper k-star-forming number SF_k(G) are both attained by V and therefore equal |V|.
The universal vertex set V is k-independent.
By definition, a set is k-independent if every vertex has strictly fewer than k neighbors in that set. For the full vertex set V (Finset.univ), the set of neighbors of any v ∈ V in Finset.univ is exactly the entire open neighborhood neighborSet v. Rewriting its cardinality into the degree of v, the condition holds immediately from the hypothesis that every vertex has degree strictly less than k.
uses
Set.ncard_eq_toFinset_card',G.neighborFinset_defhave h_ind : simple_graph_is_k_independent G k Finset.univ := by intro v _ have h_set : ({u | u ∈ (univ : Finset V) ∧ G.Adj v u} : Set V) = G.neighborSet v := by ext u simp rw [h_set, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] exact h v
The universal vertex set V is k-star-forming.
A set S is k-star-forming if every vertex v ∉ S belongs to some star with center and leaves in S ∪ {v}. For S = V (Finset.univ), no vertex lies outside V by Finset.mem_univ, so the condition is vacuously satisfied.
uses
Finset.mem_univhave h_sf_univ : simple_graph_is_k_star_forming G k Finset.univ := fun v hv => absurd (Finset.mem_univ v) hv
No proper subset of V is k-star-forming.
Assume for contradiction that some proper subset T ⊂ V is k-star-forming. Since T is a strict subset, there exists a vertex s ∉ T. By the definition of k-star-forming applied to s, there must exist a center c and a set L of k leaves adjacent to c in G. Hence L is a subset of the neighborhood of c, which implies k = |L| ≤ deg(c). But the global hypothesis guarantees deg(c) < k, a contradiction.
uses
Finset.exists_of_ssubset,Finset.mem_coe.mp,Set.ncard_le_ncard,Set.toFinite,Set.ncard_coe_finset,Set.ncard_eq_toFinset_card',G.neighborFinset_defhave h_not_sf : ∀ T ⊂ (univ : Finset V), ¬ simple_graph_is_k_star_forming G k T := by intro T hT hsf obtain ⟨s, -, hsT⟩ := Finset.exists_of_ssubset hT obtain ⟨c, L, -, -, hcard, hadj, -⟩ := hsf s hsT have h_sub : (L : Set V) ⊆ G.neighborSet c := by intro x hx exact hadj x (Finset.mem_coe.mp hx) have h_le := Set.ncard_le_ncard h_sub (Set.toFinite (G.neighborSet c)) rw [Set.ncard_coe_finset, hcard, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] at h_le have h_lt := h c change (G.neighborFinset c).card < k at h_lt omega
The universal vertex set V is minimal k-star-forming.
A set is minimal k-star-forming if it is k-star-forming and no strictly smaller subset is k-star-forming. Combining the facts that V is k-star-forming and that no proper subset of V is k-star-forming gives the result.
have h_min_sf : simple_graph_is_minimal_k_star_forming G k Finset.univ := ⟨h_sf_univ, h_not_sf⟩The k-independence number β_k(G) equals |V|.
Splitting the conjunction, the first goal is to evaluate β_k(G), the supremum of sizes of k-independent sets. By antisymmetry (le_antisymm): (1) the supremum is at most |V| via csSup_le because the set of sizes is nonempty (witnessed by V of size |V|) and every set of vertices has cardinality at most |V| (card_le_univ); (2) |V| is at most the supremum via le_csSup because the set of sizes is bounded above by |V| and contains |V| (witnessed by V, which is k-independent).
uses
le_antisymm,csSup_le,card_univ,card_le_univ,le_csSupconstructor · dsimp [simple_graph_k_independence_number] apply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, univ, h_ind, card_univ⟩ · rintro n ⟨I, -, rfl⟩ exact card_le_univ I · apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro n ⟨I, -, rfl⟩ exact card_le_univ I · exact ⟨univ, h_ind, card_univ⟩
The upper k-star-forming number SF_k(G) equals |V|.
The second goal is to evaluate SF_k(G), the supremum of sizes of minimal k-star-forming sets. Again by antisymmetry: (1) the supremum is at most |V| via csSup_le because V is a minimal k-star-forming set of size |V| and every subset has size at most |V|; (2) |V| is at most the supremum via le_csSup because the set of sizes is bounded above by |V| and contains |V| as a member.
uses
le_antisymm,csSup_le,card_univ,card_le_univ,le_csSup· dsimp [simple_graph_upper_k_star_forming_number] apply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, univ, h_min_sf, card_univ⟩ · rintro n ⟨S, -, rfl⟩ exact card_le_univ S · apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro n ⟨S, -, rfl⟩ exact card_le_univ S · exact ⟨univ, h_min_sf, card_univ⟩
Set.ncard_eq_toFinset_card'- For any set s with finite subtype, its set cardinality s.ncard equals the cardinality of its finset representation s.toFinset.card.
G.neighborFinset_def- For any vertex v in G, the finset of its neighbors is by definition the neighborhood set G.neighborSet v converted to a finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.exists_of_ssubset- If s₁ ⊂ s₂ is a strict subset, then there exists an element x ∈ s₂ such that x ∉ s₁.
Finset.mem_coe.mp- If an element belongs to the set coercion of a finset, then it belongs to the finset.
Set.ncard_le_ncard- If s ⊆ t and t is finite, then the set cardinality of s is at most the set cardinality of t.
Set.toFinite- A set whose subtype is finite is finite as a set.
Set.ncard_coe_finset- The set cardinality of a coerced finset equals its finset cardinality.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
csSup_le- The supremum of a nonempty set s is at most a if every element of s is at most a.
card_univ- The cardinality of Finset.univ equals Fintype.card α.
card_le_univ- The cardinality of any finset of α is at most Fintype.card α.
le_csSup- If a set s is bounded above, then any element in s is at most the supremum of s.
- The definitions of β_k(G) and SF_k(G) use `sSup` over sets of natural numbers rather than maximum over a finite set, requiring explicit proofs of nonemptiness and upper-boundedness before taking suprema.
- In line 25, the `omega` tactic automatically handles the linear integer arithmetic contradiction between k ≤ deg(c) and deg(c) < k.
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.
theorem simple_graph_k_independence_number_eq_card_of_degree_lt {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ v, G.degree v < k) : simple_graph_k_independence_number G k = Fintype.card V ∧ simple_graph_upper_k_star_forming_number G k = Fintype.card V := open Finset in by have h_ind : simple_graph_is_k_independent G k Finset.univ := by intro v _ have h_set : ({u | u ∈ (univ : Finset V) ∧ G.Adj v u} : Set V) = G.neighborSet v := by ext u simp rw [h_set, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] exact h v have h_sf_univ : simple_graph_is_k_star_forming G k Finset.univ := fun v hv => absurd (Finset.mem_univ v) hv have h_not_sf : ∀ T ⊂ (univ : Finset V), ¬ simple_graph_is_k_star_forming G k T := by intro T hT hsf obtain ⟨s, -, hsT⟩ := Finset.exists_of_ssubset hT obtain ⟨c, L, -, -, hcard, hadj, -⟩ := hsf s hsT have h_sub : (L : Set V) ⊆ G.neighborSet c := by intro x hx exact hadj x (Finset.mem_coe.mp hx) have h_le := Set.ncard_le_ncard h_sub (Set.toFinite (G.neighborSet c)) rw [Set.ncard_coe_finset, hcard, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] at h_le have h_lt := h c change (G.neighborFinset c).card < k at h_lt omega have h_min_sf : simple_graph_is_minimal_k_star_forming G k Finset.univ := ⟨h_sf_univ, h_not_sf⟩ constructor · dsimp [simple_graph_k_independence_number] apply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, univ, h_ind, card_univ⟩ · rintro n ⟨I, -, rfl⟩ exact card_le_univ I · apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro n ⟨I, -, rfl⟩ exact card_le_univ I · exact ⟨univ, h_ind, card_univ⟩ · dsimp [simple_graph_upper_k_star_forming_number] apply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, univ, h_min_sf, card_univ⟩ · rintro n ⟨S, -, rfl⟩ exact card_le_univ S · apply le_csSup · refine ⟨Fintype.card V, ?_⟩ rintro n ⟨S, -, rfl⟩ exact card_le_univ S · exact ⟨univ, h_min_sf, card_univ⟩