AFTD Auto-Formalizing Theoretical Domains

zero_forcing_step

def

Given a subset B of vertices in a simple graph G, the next round adds to B all vertices w such that w is the unique neighbor outside B of some vertex x in B.

Statement

def zero_forcing_step {V : Type*} (G : SimpleGraph V) (B : Set V) : Set V
Defined in
arXiv:2611.13244, Section 1 -- Stabilization of the zero forcing number of generalized Petersen graphs
Verified
12 Nov 2026
Axioms
none listed

Read back from the Lean

Given a type V, a simple graph G on V, and a subset of vertices B : Set V, zero_forcing_step G B is the set of vertices formed by the union of B with the set of all w : V such that there exists some x ∈ B whose set of neighbors outside B is exactly {w} (that is, w is the unique neighbor of x not in B).

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

/-- One round of the zero forcing color change rule: black vertices add all vertices that are the unique white neighbor of some black vertex. -/
def zero_forcing_step {V : Type*} (G : SimpleGraph V) (B : Set V) : Set V := B ∪ {w : V | ∃ x ∈ B, G.neighborSet x \ B = {w}}
See it in the graphDiscuss this resultChallenge it