AFTD Auto-Formalizing Theoretical Domains

closed_neighborhood

def

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset A : Finset V, closed_neighborhood G A is the finite set of vertices v : Finset V for which there exists some u ∈ A such that u = v or G.Adj u v.

Statement

def closed_neighborhood {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : Finset V
Defined in
arXiv:2611.01281 Section 2
Verified
04 Nov 2026
Axioms
none listed
Used by 5

Read back from the Lean

For a finite type $V$ with decidable equality, a simple graph $G$ on $V$ with decidable adjacency, and a finite set of vertices $A \subseteq V$, closed_neighborhood G A is defined as the finite set of all vertices $v \in V$ such that there exists some $u \in A$ satisfying $u = v$ or $G\text{.Adj } u\ v$ (that is, the closed neighborhood of $A$ in $G$, consisting of $A$ and all vertices adjacent to at least one vertex in $A$).

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

/-- The closed one-step neighborhood of a set of vertices in a simple graph. -/
def closed_neighborhood {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : Finset V :=
  Finset.univ.filter fun v => ∃ u ∈ A, u = v ∨ G.Adj u v
See it in the graphDiscuss this resultChallenge it