AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_like_deletion_number

deforiginal

The star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced subgraph G - X is star-like.

Statement

noncomputable def simple_graph_star_like_deletion_number {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
Related work
arXiv:2208.10475v2: The average size of a dominating set in a graph
Verified
27 Oct 2026
Axioms
none listed
Built on 1
Used by 5

Read back from the Lean

Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_star_like_deletion_number G is defined as the infimum (in ℕ) of the set of all natural numbers k for which there exists a finset X : Finset V of cardinality k such that the induced subgraph of G on the complement Xᶜ is "star-like" (simple_graph_is_star_like).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The minimum number of vertices whose deletion from G leaves an induced star-like subgraph. -/
noncomputable def simple_graph_star_like_deletion_number {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ :=
  open scoped Classical in
  sInf {k : ℕ | ∃ X : Finset V, simple_graph_is_star_like (G.induce (Xᶜ : Set V)) ∧ X.card = k}
See it in the graphDiscuss this resultChallenge it