AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it