AFTD Auto-Formalizing Theoretical Domains

is_v0

def

A vertex v of a finite simple graph G belongs to V^0(G) if removing v preserves the vertex-edge domination number, that is, gamma_ve(G - v) = gamma_ve(G).

Statement

def is_v0 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (v : V) : Prop
Defined in
arXiv:2610.26912 Section 1
Verified
21 Oct 2026
Axioms
none listed
Built on 1
  • gamma_veThe vertex-edge domination number gamma_ve(G) of a finite simple graph G is the minimum cardinality of a finite subset S of V that is a…
Used by 2
  • not_is_fix_v0_of_isolatedAn isolated vertex v in a finite simple graph G (with empty neighborhood) does not belong to V_fix^0(G).
  • is_fix_v0A vertex v of a finite simple graph G belongs to V_fix^0(G) if v is in V^0(G) and v belongs to every minimum vertex-edge dominating set S…

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V, and a vertex v : V, is_v0 G v asserts that the vertex-edge domination number gamma_ve of the induced subgraph of G on {v}ᶜ (i.e., G with vertex v removed) equals the vertex-edge domination number gamma_ve of G. Here, the vertex-edge domination number gamma_ve of a graph is the infimum (sInf) of the sizes of all finite sets S of vertices that are vertex-edge dominating, where a set S is vertex-edge dominating (is_ve_dominating) if for every edge between vertices x and y, there exists some u ∈ S such that u = x, u is adjacent to x, u = y, or u is adjacent to y.

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

/-- A vertex belongs to V^0(G) if removing it preserves the vertex-edge domination number. -/
def is_v0 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (v : V) : Prop := gamma_ve (G.induce ({v}ᶜ : Set V)) = gamma_ve G
See it in the graphDiscuss this resultChallenge it