AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_star_like

def

G is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.

Statement

def simple_graph_is_star_like {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : Prop
Defined in
arXiv:2610.11446 (On the local average order of dominating sets), Lemma 5.1 (star-like graphs: every vertex is a leaf or an l-stem with l ≤ 2).
Verified
09 Oct 2026
Axioms
none listed
Built on 1
Used by 11

Lean source view module on GitHub

/-- `G` is star-like: every vertex is a leaf (degree one) or an `l`-stem with `1 ≤ l ≤ 2`. -/
def simple_graph_is_star_like {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : Prop :=
  ∀ w, G.degree w = 1 ∨ (1 ≤ simple_graph_leaf_neighbor_count G w ∧
    simple_graph_leaf_neighbor_count G w ≤ 2)
See it in the graphDiscuss this resultChallenge it