AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_star_forming

def

A 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 contains v (v as the centre or as a leaf).

Statement

def simple_graph_is_k_star_forming {V : Type*} (G : SimpleGraph V) (k : ℕ) (S : Finset V) : Prop
Defined in
arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Definition 2.1.
Verified
14 Oct 2026
Axioms
none listed
Used by 9

Lean source view module on GitHub

/-- A vertex set `S` is `k`-star-forming when every `v ∉ S` lies in a copy of `K_{1,k}` in `G[S ∪ {v}]`. -/
def simple_graph_is_k_star_forming {V : Type*} (G : SimpleGraph V) (k : ℕ) (S : Finset V) : Prop :=
  ∀ v, v ∉ S → ∃ c : V, ∃ L : Finset V, (c = v ∨ c ∈ S) ∧ (∀ x ∈ L, x = v ∨ x ∈ S) ∧
    L.card = k ∧ (∀ x ∈ L, G.Adj c x) ∧ (v = c ∨ v ∈ L)
See it in the graphDiscuss this resultChallenge it