simple_graph_is_k_independent
def
A 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 than k neighbours in I.
Statement
def simple_graph_is_k_independent {V : Type*} (G : SimpleGraph V) (k : ℕ) (I : Finset V) : Prop
- Defined in
- arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Sec. 1 (k-independent set: Δ(G[I]) < k).
- Verified
- 14 Oct 2026
- Axioms
- none listed
- Used by 10
- simple_graph_is_k_independent_iffWith decidable adjacency, a vertex set I is k-independent iff every v ∈ I has fewer than k neighbours in the finset I.filter (G.Adj v).
- simple_graph_k_independent_is_k_independent_one_iffA vertex set is 1-independent exactly when it is independent: no two of its vertices are adjacent.
- simple_graph_is_k_independent_monoEvery subset of a k-independent vertex set is k-independent.
- exists_triangle_free_k_independence_number_lt_upper_k_star_forming_numberThere is a triangle-free graph H on 10 vertices with β_4(H) = 7 < 8 = SF_4(H).
- simple_graph_k_independence_number_eq_card_of_degree_ltIf every vertex of the finite graph G has degree less than k, then β_k(G) = SF_k(G) = |V(G)|.
- simple_graph_k_independence_numberβ_k(G): the maximum cardinality of a k-independent vertex set of G.
- simple_graph_k_independence_number_le_upper_k_star_forming_numberFor every finite graph G and every k, β_k(G) ≤ SF_k(G).
- simple_graph_is_k_independent_emptyThe empty vertex set is k-independent, for every k.
- complete_bipartite_k_independence_number_eq_upper_k_star_forming_numberFor k ≥ 2 and a, b ≥ k, the complete bipartite graph K_{a,b} has β_k(K_{a,b}) = SF_k(K_{a,b}) = max{a, b, 2k − 2}.
- chain_graph_two_independence_number_eq_upper_two_star_forming_numberFor every finite chain graph G, the dissociation number β₂(G) equals the upper 2-star-forming number SF₂(G).
Lean source view module on GitHub
/-- A vertex set `I` is `k`-independent when `G[I]` has maximum degree less than `k`. -/ def simple_graph_is_k_independent {V : Type*} (G : SimpleGraph V) (k : ℕ) (I : Finset V) : Prop := ∀ v ∈ I, ({u | u ∈ I ∧ G.Adj v u} : Set V).ncard < k