AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_perfect_dominating

def

A subset D of vertices in a simple graph G is a perfect dominating set if every vertex v of G is dominated by exactly one vertex in D, that is, there exists a unique u in D such that u is adjacent to v or u equals v.

Statement

def simple_graph_is_perfect_dominating {V : Type*} (G : SimpleGraph V) (D : Set V) : Prop
Defined in
arXiv:2611.11191, Section 2
Verified
11 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a simple graph $G$ on a vertex type $V$ and a subset of vertices $D \subseteq V$, the definition asserts that for every vertex $v \in V$, there exists a unique vertex $u \in V$ such that $u \in D$ and either $v$ is adjacent to $u$ in $G$ or $v = u$. That is, every vertex in $V$ has exactly one neighbor (in the closed neighborhood sense) in $D$.

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 subset D of vertices in a simple graph G is a perfect dominating set if every vertex is dominated by a unique element of D. -/
def simple_graph_is_perfect_dominating {V : Type*} (G : SimpleGraph V) (D : Set V) : Prop := ∀ v : V, ∃! u ∈ D, G.Adj v u ∨ v = u
See it in the graphDiscuss this resultChallenge it