zfs_compl_iff_no_stuck
For any finite graph G and finite T, the complement V\T is a zero forcing set precisely when T contains no nonempty "stuck" subset W, i.e. no nonempty W ⊆ T such that every vertex outside W is adjacent to at most one vertex of W (or to any given w it never sees w as its unique W-neighbour).
Statement
theorem zfs_compl_iff_no_stuck {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (T : Finset V) : is_zero_forcing_set G ((Finset.univ \ T : Finset V) : Set V) ↔ ¬ ∃ W : Finset V, W.Nonempty ∧ W ⊆ T ∧ (∀ u : V, u ∉ W → ∀ w : V, w ∈ W → G.Adj u w → ∃ x : V, x ∈ W ∧ G.Adj u x ∧ x ≠ w)
- Source
- step towards gt_zero_forcing_poly_not_unimodal
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
- 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.
- Used by 5
- root_exposed_fort_iff_new_white_leaf_breaks_forcingIf the complement of W is a zero forcing set of G, then W contains a root-exposed fort exactly when the same originally blue vertices fail…
- tree_fort_free_nonpure_counterexampleA four-vertex tree has a maximal fort-free two-set and also a fort-free three-set.
- tree_four_zf_white_rank_sequence_counterexampleThere exists a four-vertex tree for which no matroid on its vertex set has the same numbers of independent sets of each size as the…
- zero_forcing_pair_obstruction_transitiveFor three distinct vertices each of whose singleton white sets is fort-free, the relation that a two-vertex white set is not fort-free is…
- tree_zf_white_rank_pair_positive_correlationThere is a six-vertex tree and two vertices such that, among the four-element white sets whose complements are zero forcing, the events…
The proof, explained
The complement S = V \ T is a zero forcing set if and only if T contains no stuck subset (fort). For the forward direction, an auxiliary induction shows that no vertex in a fort disjoint from the initial set can ever be forced; hence if T contained a nonempty fort W, vertices in W could never be forced, contradicting that S forces every vertex. In the reverse direction, if S fails to force all vertices, the set W of unforced vertices is nonempty, contained in T, and satisfies the fort property, which contradicts the hypothesis that T contains no such subset.
In the auxiliary lemma `zf_fort_blocking_induct`, establish the base case: initial vertices in S cannot belong to the fort F.
We proceed by induction on the derivation of `ZeroForced G S v`. In the base case (`ZeroForced.init`), the vertex v belongs to the initial set S. Because the hypothesis `hdisjoint` specifies that F and S are disjoint, v cannot belong to F.
intro v hv induction hv with | init v hvS => intro hvF exact hdisjoint v hvF hvS
Establish the inductive step of `zf_fort_blocking_induct`: a forced vertex cannot force a vertex into the fort F.
In the induction step, u is an already forced vertex adjacent to w, and all neighbors of u other than w are already forced. By the induction hypothesis for u, u ∉ F. Assuming for contradiction that w ∈ F, the fort property `hfort` implies that u must have another neighbor x ∈ F with x ≠ w. However, the induction hypothesis for the other neighbors of u asserts that x ∉ F, yielding a contradiction.
| step u w hu huw hothers ihu ihothers => intro hwF obtain ⟨x, hxF, hux, hxw⟩ := hfort u ihu w hwF huw exact ihothers x hux hxw hxFSet up the equivalence by defining S = V \ T and splitting into both directions of the if-and-only-if.
We enable classical logic, define S as the set complement of T in the universal finset, rewrite the goal in terms of S, and use `constructor` to separate the forward and backward implications.
classical let S : Set V := ((Finset.univ \ T : Finset V) : Set V) change is_zero_forcing_set G S ↔ _ constructor
If V \ T is a zero forcing set, then T contains no nonempty fort.
Assume S = V \ T is a zero forcing set, and suppose for contradiction that there exists a nonempty fort W ⊆ T containing some vertex v. Since W ⊆ T, no element of W belongs to S = V \ T, so W and S are disjoint (by `Finset.mem_sdiff.mp`). By `zf_fort_blocking_induct`, no vertex in W can ever be forced from S. But since S is a zero forcing set, every vertex including v is forced, contradicting v ∈ W.
uses
Finset.mem_sdiff.mp,zf_fort_blocking_induct· intro h ⟨W, ⟨v, hv⟩, hWT, hfort⟩ have hd : ∀ x, x ∈ (W : Set V) → x ∉ S := by intro x hxW hxS exact (Finset.mem_sdiff.mp hxS).2 (hWT hxW) exact zf_fort_blocking_induct G S (W : Set V) hd hfort v (h v) hv
Assuming S fails to force all vertices, define the set W of unforced vertices and show that W is a nonempty subset of T.
Assume T contains no nonempty fort. To show S is a zero forcing set, suppose for contradiction that some vertex v is not forced. Define W to be the set of all unforced vertices; W is nonempty because it contains v. Furthermore, W ⊆ T: if some x ∈ W were not in T, then x would belong to S = V \ T, so x would be forced initially by `ZeroForced.init`, contradicting that x is unforced.
uses
Finset.mem_filter.mp,ZeroForced.init· intro h v by_contra hv let W : Finset V := Finset.univ.filter (fun x => ¬ ZeroForced G S x) have hW : W.Nonempty := ⟨v, by simp [W, hv]⟩ have hWT : W ⊆ T := by intro x hx have hnx : ¬ ZeroForced G S x := (Finset.mem_filter.mp hx).2 by_contra hxT apply hnx exact ZeroForced.init x (by simp [S, hxT])
Show that the unforced set W satisfies the fort condition, contradicting the assumption that T contains no nonempty fort.
Let u ∉ W and w ∈ W be adjacent. Because u ∉ W, u is forced. If u had no other neighbor in W, then all neighbors x ≠ w of u would be outside W, hence already forced (using `Finset.mem_filter.mpr` and `Finset.mem_univ`). By the zero forcing rule `ZeroForced.step`, u would then force w, which contradicts w ∈ W (using `Finset.mem_filter.mp`). Thus u must have another neighbor in W with x ≠ w, proving that W is a fort. Since W is a nonempty fort contained in T, this contradicts the hypothesis and completes the proof.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mp,ZeroForced.stephave hfort : ∀ u : V, u ∉ W → ∀ w : V, w ∈ W → G.Adj u w → ∃ x : V, x ∈ W ∧ G.Adj u x ∧ x ≠ w := by intro u hu w hw huw have huS : ZeroForced G S u := by by_contra hnu apply hu exact Finset.mem_filter.mpr ⟨Finset.mem_univ u, hnu⟩ by_contra hn have hall : ∀ x, G.Adj u x → x ≠ w → ZeroForced G S x := by intro x hux hxw by_contra hnx apply hn exact ⟨x, Finset.mem_filter.mpr ⟨Finset.mem_univ x, hnx⟩, hux, hxw⟩ exact (Finset.mem_filter.mp hw).2 (ZeroForced.step u w huS huw hall) exact h ⟨W, hW, hWT, hfort⟩
Finset.mem_sdiff.mp- An element of a set difference A \ B belongs to A and does not belong to B.
zf_fort_blocking_induct- If a set of vertices F is disjoint from S and satisfies the fort condition (every vertex outside F adjacent to F has at least two neighbors in F), then no vertex forced from S can belong to F.
Finset.mem_filter.mp- An element in a filtered finite set satisfies the filtering predicate.
ZeroForced.init- Every vertex belonging to the initial set S is forced.
Finset.mem_filter.mpr- An element belonging to a finite set and satisfying a predicate belongs to the filtered finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
ZeroForced.step- If a vertex u is forced, u is adjacent to w, and all other neighbors of u are already forced, then w is forced.
- The file includes an auxiliary inductive lemma, `zf_fort_blocking_induct`, immediately before the main theorem, which establishes that a fort disjoint from the initial set can never be forced.
- Complement sets and filters are formalized using finsets coerced to sets (`Set V`), using explicit lemmas such as `Finset.mem_sdiff.mp` and `Finset.mem_filter.mp` to relate set membership to logical properties.
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.
open SimpleGraphprivate theorem zf_fort_blocking_induct {V : Type*} (G : SimpleGraph V) (S F : Set V) (hdisjoint : ∀ v, v ∈ F → v ∉ S) (hfort : ∀ u, u ∉ F → ∀ w, w ∈ F → G.Adj u w → ∃ x, x ∈ F ∧ G.Adj u x ∧ x ≠ w) : ∀ v, ZeroForced G S v → v ∉ F := by intro v hv induction hv with | init v hvS => intro hvF exact hdisjoint v hvF hvS | step u w hu huw hothers ihu ihothers => intro hwF obtain ⟨x, hxF, hux, hxw⟩ := hfort u ihu w hwF huw exact ihothers x hux hxw hxFtheorem zfs_compl_iff_no_stuck {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (T : Finset V) : is_zero_forcing_set G ((Finset.univ \ T : Finset V) : Set V) ↔ ¬ ∃ W : Finset V, W.Nonempty ∧ W ⊆ T ∧ (∀ u : V, u ∉ W → ∀ w : V, w ∈ W → G.Adj u w → ∃ x : V, x ∈ W ∧ G.Adj u x ∧ x ≠ w) := by classical let S : Set V := ((Finset.univ \ T : Finset V) : Set V) change is_zero_forcing_set G S ↔ _ constructor · intro h ⟨W, ⟨v, hv⟩, hWT, hfort⟩ have hd : ∀ x, x ∈ (W : Set V) → x ∉ S := by intro x hxW hxS exact (Finset.mem_sdiff.mp hxS).2 (hWT hxW) exact zf_fort_blocking_induct G S (W : Set V) hd hfort v (h v) hv · intro h v by_contra hv let W : Finset V := Finset.univ.filter (fun x => ¬ ZeroForced G S x) have hW : W.Nonempty := ⟨v, by simp [W, hv]⟩ have hWT : W ⊆ T := by intro x hx have hnx : ¬ ZeroForced G S x := (Finset.mem_filter.mp hx).2 by_contra hxT apply hnx exact ZeroForced.init x (by simp [S, hxT]) have hfort : ∀ u : V, u ∉ W → ∀ w : V, w ∈ W → G.Adj u w → ∃ x : V, x ∈ W ∧ G.Adj u x ∧ x ≠ w := by intro u hu w hw huw have huS : ZeroForced G S u := by by_contra hnu apply hu exact Finset.mem_filter.mpr ⟨Finset.mem_univ u, hnu⟩ by_contra hn have hall : ∀ x, G.Adj u x → x ≠ w → ZeroForced G S x := by intro x hux hxw by_contra hnx apply hn exact ⟨x, Finset.mem_filter.mpr ⟨Finset.mem_univ x, hnx⟩, hux, hxw⟩ exact (Finset.mem_filter.mp hw).2 (ZeroForced.step u w huS huw hall) exact h ⟨W, hW, hWT, hfort⟩