AFTD Auto-Formalizing Theoretical Domains

zero_forcing_boundary_monotonicity

theoremverifiedformalization

Let G be a simple graph, and let S be a finite subset of vertices. In the zero forcing sequence B_0 = S ⊆ B_1 ⊆ ..., the extended cardinality of ∂B_{i+1} is at most that of ∂B_i for every i ≥ 0. In particular, the extended cardinality of ∂B_i is at most that of S for every i ≥ 0, and the extended cardinality of ∂cl(S) is at most that of S.

Statement

theorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard
Formalizes
arXiv:2611.13244, Proposition 2.9 -- Stabilization of the zero forcing number of generalized Petersen graphs
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • zero_forcing_boundaryFor a simple graph G and a subset X of vertices, the boundary ∂X is the set of all vertices x in X that have a neighbor outside X.
  • zero_forcing_seqThe sequence of vertex subsets B_i in a simple graph G starting with B_0 = S and iteratively defined by adding all unique outside…
  • zero_forcing_clThe zero forcing closure cl(S) of a subset S of vertices in a simple graph G is the union over all natural numbers i of B_i.
  • zero_forcing_boundary_monoLet G be a simple graph and S a finite subset of vertices. Then for every natural number i, the extended cardinality of the boundary…
  • zero_forcing_boundary_cl_leLet G be a simple graph and S a finite subset of vertices. Then the extended cardinality of the boundary of the closure cl(S) is at most…

Read back from the Lean

Let $V$ be a type, $G$ be a simple graph on $V$, and $S \subseteq V$ be a finite set of vertices. Then all three of the following hold: 1. For all $i \in \mathbb{N}$, the extended cardinality of the zero-forcing boundary of the $(i + 1)$-th step of the zero-forcing sequence of $S$ in $G$ is less than or equal to the extended cardinality of the zero-forcing boundary of the $i$-th step. 2. For all $i \in \mathbb{N}$, the extended cardinality of the zero-forcing boundary of the $i$-th step of the zero-forcing sequence of $S$ in $G$ is less than or equal to the extended cardinality of $S$. 3. The extended cardinality of the zero-forcing boundary of the zero-forcing closure of $S$ in $G$ is less than or equal to the extended cardinality of $S$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem combines three boundary monotonicity properties of zero forcing into a single statement: the boundary size cannot increase from one step to the next, each intermediate boundary size is bounded by |S|, and the boundary size of the closure cl(S) is bounded by |S|. The proof directly constructs the 3-tuple of conjunctions from three constituent lemmas proved earlier.

  1. The boundary monotonicity properties hold: |∂B_{i+1}| ≤ |∂B_i| for all i ≥ 0, |∂B_i| ≤ |S| for all i ≥ 0, and |∂cl(S)| ≤ |S|.

    The claim is a conjunction of three statements, proved by pairing together three previously established theorems: `zero_forcing_boundary_mono` gives step-by-step non-expansion of the boundary, `zero_forcing_boundary_cl_le_seq_le` bounds the boundary at each finite step by |S|, and `zero_forcing_boundary_cl_le` bounds the boundary of the closure cl(S) by |S|.

    line 2

    uses zero_forcing_boundary_mono, zero_forcing_boundary_cl_le_seq_le, zero_forcing_boundary_cl_le

    theorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := ⟨zero_forcing_boundary_mono G hS, zero_forcing_boundary_cl_le_seq_le G hS, zero_forcing_boundary_cl_le G hS⟩
zero_forcing_boundary_mono
For any finite vertex subset S of a graph G and any index i, the extended cardinality of the boundary of the (i+1)-th zero forcing set is at most that of the i-th zero forcing set.
zero_forcing_boundary_cl_le_seq_le
For any finite vertex subset S of a graph G and any index N, the extended cardinality of the boundary of the N-th zero forcing set is at most the cardinality of S.
zero_forcing_boundary_cl_le
For any finite vertex subset S of a graph G, the extended cardinality of the boundary of the zero forcing closure cl(S) is at most the cardinality of S.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Boundary monotonicity along the zero forcing process: |∂B_{i+1}| ≤ |∂B_i| for all i, |∂B_i| ≤ |S| for all i, and |∂cl(S)| ≤ |S|. -/theorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := ⟨zero_forcing_boundary_mono G hS, zero_forcing_boundary_cl_le_seq_le G hS, zero_forcing_boundary_cl_le G hS⟩
See it in the graphDiscuss this resultChallenge it