AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_dominating

def

A subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.

Statement

def simple_graph_is_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
Defined in
arXiv:2610.28936 Definition 2.1
Verified
25 Oct 2026
Axioms
none listed
Used by 15

Read back from the Lean

Given a type V, a simple graph G on V, and a subset S of V, simple_graph_is_dominating G S is defined to hold if and only if for every vertex v : V, either v ∈ S or there exists some u ∈ S such that u is adjacent to v in G (G.Adj u v). (That is, S is a dominating set of 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

/-- Predicate that a set of vertices is a dominating set in a simple graph. -/
def simple_graph_is_dominating {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ v : V, v ∈ S ∨ ∃ u ∈ S, G.Adj u v
See it in the graphDiscuss this resultChallenge it