AFTD Auto-Formalizing Theoretical Domains

is_zero_forcing_set_mono

theoremverified

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

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.

  1. 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.

    lines 3–7

    uses ZeroForced.init, ZeroForced.step

      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
  2. 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'.

    lines 12–13

    uses zf_mono_inclusion_induction

      intro 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

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)
See it in the graphDiscuss this resultChallenge it