AFTD Auto-Formalizing Theoretical Domains

zero_forcing_finset_step

def

One executable parallel zero forcing step from a finite blue set: include each vertex with a blue neighbor whose other neighbors are blue.

Statement

def zero_forcing_finset_step {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : Finset V
Source
Filed by the prover as a step towards another result
Verified
13 Nov 2026
Axioms
none listed
Used by 3
  • zero_forcing_finset_iterThe finite blue set obtained by iterating the executable parallel zero forcing step k times.
  • zero_forcing_finset_iter_decidesA blue set is zero forcing exactly when the executable parallel forcing process colors every vertex after at most the number of vertices…
  • zero_forcing_finset_iter_of_stableIf a finite parallel forcing iteration has stabilized, the original blue set is zero forcing exactly when the stabilized set is all…

Lean source view module on GitHub

def zero_forcing_finset_step {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : Finset V := S ∪ Finset.univ.filter (fun w => ∃ u ∈ S, G.Adj u w ∧ ∀ x, G.Adj u x → x ≠ w → x ∈ S)
See it in the graphDiscuss this resultChallenge it