AFTD Auto-Formalizing Theoretical Domains

pend_ve_num

def

a_C is the minimum cardinality of a vertex set A' contained in the component part C such that A' together with v ve-dominates the induced subgraph on C together with v.

Statement

noncomputable def pend_ve_num {V : Type*} [Fintype V] (G : SimpleGraph V) (A : Set V) (v : V) : ℕ
Source
step towards not_is_fix_v0_of_neighbors_unreachable
Verified
21 Oct 2026
Axioms
none listed
Built on 1
  • ve_dominates_insideA vertex set S ve-dominates inside a vertex set A if every edge of G with both endpoints in A is ve-dominated by a vertex of S.

Lean source view module on GitHub

/-- The minimum size of a set `S ⊆ A` such that `S ∪ {v}` ve-dominates all edges inside `A ∪ {v}`; the paper's pendant parameter `a_C`. -/
noncomputable def pend_ve_num {V : Type*} [Fintype V] (G : SimpleGraph V) (A : Set V) (v : V) : ℕ := sInf {k : ℕ | ∃ S : Finset V, (S : Set V) ⊆ A ∧
    ve_dominates_inside G ((S : Set V) ∪ {v}) (A ∪ {v}) ∧ S.card = k}
See it in the graphDiscuss this resultChallenge it