is_zero_forcing_set_mono
If S is a zero forcing set of a simple graph G and S is a subset of S', then S' is also a zero forcing set of G.
Statement
theorem is_zero_forcing_set_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V} (h : S ⊆ S') (hS : is_zero_forcing_set G S) : is_zero_forcing_set G S'
- Source
- arXiv:2611.11352 Sec. 1
- Verified
- 13 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
- Used by 2
- tree_exposure_plain_partial_sync_counterexampleFor a rooted three-vertex path the unexposed counts at ranks zero and one are one and three, while the exposed counts at ranks zero, one…
- zero_forcing_poly_positive_coeff_intervalFor any finite graph the positive coefficients of its zero forcing polynomial form an interval.
Read back from the Lean
For any type V, any simple graph G on V, and any subsets S, S' : Set V, if S ⊆ S' and S is a zero forcing set for G (that is, every vertex in V is zero-forced from S), then S' is also a zero forcing set for G.
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 is proved by first establishing an auxiliary lemma: if S ⊆ T, then every vertex forced by S is also forced by T. This lemma is proved by induction on the definition of a forced vertex, where elements initially in S belong to T, and each propagation step remains valid from T by the induction hypotheses. Since S is assumed to be a zero forcing set, it forces all vertices of G, so by the auxiliary lemma S' also forces all vertices of G, making S' a zero forcing set.
If S ⊆ T, then every vertex forced by S is also forced by T.
We fix a vertex v and assume it is forced by S, proceeding by induction on the derivation of ZeroForced G S v: - Base case (init): If v ∈ S, then v ∈ T because S ⊆ T, so v is initially forced from T by ZeroForced.init. - Inductive step (step): If w is forced from S by an already-forced neighbor u whose other neighbors are all forced from S, the induction hypotheses show that u and each of those neighbors are already forced from T. Hence u can force w from T as well, using ZeroForced.step.
uses
ZeroForced.init,ZeroForced.stepintro v hv induction hv with | init v hvS => exact ZeroForced.init v (h hvS) | step u w hu huw hothers ihu ihothers => exact ZeroForced.step u w ihu huw ihothers
Every vertex of G is forced by S', so S' is a zero forcing set of G.
To show that S' is a zero forcing set, we consider an arbitrary vertex v of G. Since S is a zero forcing set (hS), v is forced from S. Applying the monotonicity lemma zf_mono_inclusion_induction with the inclusion S ⊆ S' (h), it follows that v is also forced from S'.
uses
zf_mono_inclusion_inductionintro v exact zf_mono_inclusion_induction G h v (hS v)
ZeroForced.init- Every vertex belonging to the initial set S is forced by S.
ZeroForced.step- If a vertex u is forced by S, u is adjacent to w, and all other neighbors of u are forced by S, then w is also forced by S.
zf_mono_inclusion_induction- If S ⊆ T, then every vertex forced by S is also forced by T.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private theorem zf_mono_inclusion_induction {V : Type*} (G : SimpleGraph V) {S T : Set V} (h : S ⊆ T) : ∀ v, ZeroForced G S v → ZeroForced G T v := by intro v hv induction hv with | init v hvS => exact ZeroForced.init v (h hvS) | step u w hu huw hothers ihu ihothers => exact ZeroForced.step u w ihu huw ihothers/-- Supersets of zero forcing sets are zero forcing sets. -/theorem is_zero_forcing_set_mono {V : Type*} (G : SimpleGraph V) {S S' : Set V} (h : S ⊆ S') (hS : is_zero_forcing_set G S) : is_zero_forcing_set G S' := by intro v exact zf_mono_inclusion_induction G h v (hS v)