AFTD Auto-Formalizing Theoretical Domains

simple_graph_k_independence_number

def

β_k(G): the maximum cardinality of a k-independent vertex set of G.

Statement

noncomputable def simple_graph_k_independence_number {V : Type*} (G : SimpleGraph V) (k : ℕ) : ℕ
Defined in
arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Sec. 1 (β_k).
Verified
14 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 5

Lean source view module on GitHub

/-- `β_k(G)`: the maximum cardinality of a `k`-independent vertex set. -/
noncomputable def simple_graph_k_independence_number {V : Type*} (G : SimpleGraph V) (k : ℕ) : ℕ :=
  sSup {n | ∃ I : Finset V, simple_graph_is_k_independent G k I ∧ I.card = n}
See it in the graphDiscuss this resultChallenge it