AFTD Auto-Formalizing Theoretical Domains

is_ve_dominating

def

A subset S of vertices in a simple graph G is a vertex-edge dominating set if for all vertices x and y with G.Adj x y, there exists u in S such that u = x, or G.Adj u x, or u = y, or G.Adj u y.

Statement

def is_ve_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
Defined in
arXiv:2610.26912 Section 1
Verified
21 Oct 2026
Axioms
none listed
Used by 3
  • 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…
  • 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…

Read back from the Lean

Given a type V, a simple graph G on V, and a subset S of V, is_ve_dominating G S asserts that for every pair of vertices x, y : V, if x and y are adjacent in G, then there exists some vertex u ∈ S such that u = x, u is adjacent to x in G, u = y, or u is adjacent to y in G.

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 set S is a vertex-edge dominating set if every edge has an endpoint in the closed neighborhood of some vertex in S. -/
def is_ve_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ ⦃x y : V⦄, G.Adj x y → ∃ u ∈ S, u = x ∨ G.Adj u x ∨ u = y ∨ G.Adj u y
See it in the graphDiscuss this resultChallenge it