zero_forcing_boundary_mono
Let G be a simple graph and S a finite subset of vertices. Then for every natural number i, the extended cardinality of the boundary ∂B_{i+1} is at most the extended cardinality of the boundary ∂B_i.
Statement
theorem zero_forcing_boundary_mono {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
- 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 2
- 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…
- Used by 2
- zero_forcing_boundary_monotonicityLet 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…
- 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
For any type V, any simple graph G on V, and any subset S : Set V, if S is finite (hS : S.Finite), then for every natural number i : ℕ, the extended cardinality (encard) of the zero-forcing boundary of the (i + 1)-th term 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 term of the zero-forcing sequence of S in 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
To show that the boundary size is non-increasing along the zero forcing sequence (|∂B_{i+1}| ≤ |∂B_i|), the proof constructs an explicit injection f from ∂B_{i+1} to ∂B. Each newly forced vertex w ∈ W = B_{i+1} \ B is mapped to a chosen vertex in B that forced it, while vertices already in B (and not in W) are mapped to themselves. Injectivity holds because forcing vertices uniquely identify the vertices they forced and can never belong to the new boundary ∂B_{i+1}, preventing any collision between new and old boundary vertices.
Let B = B_i and let W be the set of newly forced vertices; define a map f : V → V that sends each w ∈ W to a vertex x ∈ B that forces w, and fixes all vertices not in W.
By definition of the zero forcing sequence, B_{i+1} = B ∪ W, where W consists of vertices w for which some x ∈ B has N(x) \ B = {w}. Using classical choice, f selects one such forcing vertex x for each w ∈ W, and acts as the identity on vertices outside W. Rewriting with `dif_pos` and `dif_neg` gives the value of f on and off W.
uses
dif_pos,dif_negclassical have _ := hS set B := zero_forcing_seq G S i set W := {w : V | ∃ x ∈ B, G.neighborSet x \ B = {w}} have hB' : zero_forcing_seq G S (i + 1) = B ∪ W := rfl have hW : ∀ w ∈ W, ∃ x ∈ B, G.neighborSet x \ B = {w} := fun w hw => hw let f : V → V := fun w => if hw : w ∈ W then Classical.choose (hW w hw) else w have hf_W : ∀ (w : V) (hw : w ∈ W), f w = Classical.choose (hW w hw) := fun w hw => dif_pos hw have hf_not_W : ∀ (w : V) (hw : w ∉ W), f w = w := fun w hw => dif_neg hw
If x ∈ B forces a vertex w ∈ W, then x cannot belong to the boundary ∂(B ∪ W).
If x were in ∂(B ∪ W), it would have a neighbor y ∉ B ∪ W. In particular, y ∉ B (by `Set.mem_union_left`), so y ∈ N(x) \ B = {w}, meaning y = w (by `Set.mem_singleton_iff`). But w ∈ W ⊆ B ∪ W (by `Set.mem_union_right`), which contradicts y ∉ B ∪ W.
uses
Set.mem_union_left,Set.mem_singleton_iff,Set.mem_union_righthave h_not_in_boundary : ∀ (w : V) (x : V) (hxB : x ∈ B) (hx : G.neighborSet x \ B = {w}), x ∉ zero_forcing_boundary G (B ∪ W) := by intro w x hxB hx h rw [zero_forcing_boundary] at h rcases h with ⟨-, y, hy_adj, hy_notin⟩ have hy_notin_B : y ∉ B := fun hyB => hy_notin (Set.mem_union_left _ hyB) have hy_diff : y ∈ G.neighborSet x \ B := ⟨hy_adj, hy_notin_B⟩ rw [hx, Set.mem_singleton_iff] at hy_diff subst hy_diff exact hy_notin (Set.mem_union_right _ ⟨x, hxB, hx⟩)
If x ∈ B forces a vertex w ∈ W, then x belongs to the boundary ∂B.
By assumption x ∈ B. Since N(x) \ B = {w}, the vertex w is a neighbor of x and w ∉ B (using `Set.mem_singleton`), so w witnesses that x has an external neighbor with respect to B.
uses
Set.mem_singletonhave h_in_boundary_of_W : ∀ (w : V) (x : V) (hxB : x ∈ B) (hx : G.neighborSet x \ B = {w}), x ∈ zero_forcing_boundary G B := by intro w x hxB hx rw [zero_forcing_boundary] refine ⟨hxB, w, ?_, ?_⟩ · have hw : w ∈ G.neighborSet x \ B := by rw [hx]; exact Set.mem_singleton w exact hw.1 · have hw : w ∈ G.neighborSet x \ B := by rw [hx]; exact Set.mem_singleton w exact hw.2
Any vertex v in the boundary ∂(B ∪ W) that does not belong to W must belong to ∂B.
Since v ∈ B ∪ W and v ∉ W, we have v ∈ B (using `False.elim` to rule out v ∈ W). Any neighbor y of v outside B ∪ W is also outside B (by `Set.mem_union_left`), so y witnesses that v ∈ ∂B.
uses
False.elim,Set.mem_union_lefthave h_in_boundary_of_not_W : ∀ (v : V), v ∈ zero_forcing_boundary G (B ∪ W) → v ∉ W → v ∈ zero_forcing_boundary G B := by intro v hv hvnw rw [zero_forcing_boundary] at hv ⊢ rcases hv with ⟨hvBW, y, hy_adj, hy_notin⟩ have hvB : v ∈ B := by cases hvBW with | inl h => exact h | inr h => exact False.elim (hvnw h) refine ⟨hvB, y, hy_adj, fun hyB => hy_notin (Set.mem_union_left _ hyB)⟩
The function f maps the boundary ∂(B ∪ W) into the boundary ∂B.
Let v ∈ ∂(B ∪ W). If v ∈ W, f(v) is a chosen vertex in B forcing v (by `Classical.choose_spec`), which belongs to ∂B by the third step. If v ∉ W, f(v) = v, which belongs to ∂B by the fourth step.
uses
Classical.choose_spechave h_maps : Set.MapsTo f (zero_forcing_boundary G (B ∪ W)) (zero_forcing_boundary G B) := by intro v hv by_cases hw : v ∈ W · rw [hf_W v hw] have hspec := Classical.choose_spec (hW v hw) exact h_in_boundary_of_W v (Classical.choose (hW v hw)) hspec.1 hspec.2 · rw [hf_not_W v hw] exact h_in_boundary_of_not_W v hv hw
The function f is injective on the boundary ∂(B ∪ W).
Suppose u, v ∈ ∂(B ∪ W) satisfy f(u) = f(v). If both u, v ∈ W, then {u} = N(f(u)) \ B = N(f(v)) \ B = {v} (by `Classical.choose_spec`), so u = v by `Set.singleton_eq_singleton_iff.mp`. If u ∈ W but v ∉ W, then f(u) = f(v) = v ∈ ∂(B ∪ W), contradicting the fact that the forcing vertex f(u) cannot lie in ∂(B ∪ W); the symmetric case v ∈ W, u ∉ W is ruled out identically (using `False.elim`). If neither belongs to W, u = f(u) = f(v) = v.
uses
Classical.choose_spec,Set.singleton_eq_singleton_iff.mp,False.elimhave h_inj : Set.InjOn f (zero_forcing_boundary G (B ∪ W)) := by intro u hu v hv heq by_cases huW : u ∈ W <;> by_cases hvW : v ∈ W · rw [hf_W u huW, hf_W v hvW] at heq have hu_spec := Classical.choose_spec (hW u huW) have hv_spec := Classical.choose_spec (hW v hvW) have h_eq_sets : ({u} : Set V) = {v} := by rw [← hu_spec.2, heq, hv_spec.2] exact Set.singleton_eq_singleton_iff.mp h_eq_sets · rw [hf_W u huW, hf_not_W v hvW] at heq have hu_spec := Classical.choose_spec (hW u huW) have h_u_notin := h_not_in_boundary u (Classical.choose (hW u huW)) hu_spec.1 hu_spec.2 rw [heq] at h_u_notin exact False.elim (h_u_notin hv) · rw [hf_not_W u huW, hf_W v hvW] at heq have hv_spec := Classical.choose_spec (hW v hvW) have h_v_notin := h_not_in_boundary v (Classical.choose (hW v hvW)) hv_spec.1 hv_spec.2 rw [← heq] at h_v_notin exact False.elim (h_v_notin hu) · rw [hf_not_W u huW, hf_not_W v hvW] at heq exact heq
The extended cardinality of ∂B_{i+1} is at most the extended cardinality of ∂B_i.
Since B_{i+1} = B ∪ W and f is an injection from ∂(B ∪ W) into ∂B, `Set.encard_le_encard_of_injOn` immediately yields |∂B_{i+1}| ≤ |∂B_i|.
uses
Set.encard_le_encard_of_injOnrw [hB'] exact Set.encard_le_encard_of_injOn h_maps h_inj
dif_pos- In a dependent if-then-else expression, if the condition is true, the expression reduces to the value of the 'then' branch.
dif_neg- In a dependent if-then-else expression, if the condition is false, the expression reduces to the value of the 'else' branch.
Set.mem_union_left- An element of a set a is an element of the union a ∪ b.
Set.mem_union_right- An element of a set b is an element of the union a ∪ b.
Set.mem_singleton_iff- An element belongs to the singleton {b} if and only if it equals b.
Set.mem_singleton- Any element a belongs to the singleton set {a}.
False.elim- From a proof of False, any proposition follows.
Classical.choose_spec- The witness chosen by Classical.choose satisfies the property stated in the existential statement.
Set.singleton_eq_singleton_iff.mp- If two singletons {u} and {v} are equal, then their elements u and v are equal.
Set.encard_le_encard_of_injOn- If f maps s into t and is injective on s, then the extended cardinality of s is at most that of t.
- Although the theorem includes the hypothesis that S is finite (`hS : S.Finite`), this hypothesis is unused in the proof: the inequality holds for arbitrary sets because extended cardinality (`encard`) takes values in ℕ ∪ {∞}.
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.
/-- The boundary size is monotonically non-increasing along the zero forcing sequence: |∂B_{i+1}| ≤ |∂B_i| for every i. -/theorem zero_forcing_boundary_mono {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 := by classical have _ := hS set B := zero_forcing_seq G S i set W := {w : V | ∃ x ∈ B, G.neighborSet x \ B = {w}} have hB' : zero_forcing_seq G S (i + 1) = B ∪ W := rfl have hW : ∀ w ∈ W, ∃ x ∈ B, G.neighborSet x \ B = {w} := fun w hw => hw let f : V → V := fun w => if hw : w ∈ W then Classical.choose (hW w hw) else w have hf_W : ∀ (w : V) (hw : w ∈ W), f w = Classical.choose (hW w hw) := fun w hw => dif_pos hw have hf_not_W : ∀ (w : V) (hw : w ∉ W), f w = w := fun w hw => dif_neg hw have h_not_in_boundary : ∀ (w : V) (x : V) (hxB : x ∈ B) (hx : G.neighborSet x \ B = {w}), x ∉ zero_forcing_boundary G (B ∪ W) := by intro w x hxB hx h rw [zero_forcing_boundary] at h rcases h with ⟨-, y, hy_adj, hy_notin⟩ have hy_notin_B : y ∉ B := fun hyB => hy_notin (Set.mem_union_left _ hyB) have hy_diff : y ∈ G.neighborSet x \ B := ⟨hy_adj, hy_notin_B⟩ rw [hx, Set.mem_singleton_iff] at hy_diff subst hy_diff exact hy_notin (Set.mem_union_right _ ⟨x, hxB, hx⟩) have h_in_boundary_of_W : ∀ (w : V) (x : V) (hxB : x ∈ B) (hx : G.neighborSet x \ B = {w}), x ∈ zero_forcing_boundary G B := by intro w x hxB hx rw [zero_forcing_boundary] refine ⟨hxB, w, ?_, ?_⟩ · have hw : w ∈ G.neighborSet x \ B := by rw [hx]; exact Set.mem_singleton w exact hw.1 · have hw : w ∈ G.neighborSet x \ B := by rw [hx]; exact Set.mem_singleton w exact hw.2 have h_in_boundary_of_not_W : ∀ (v : V), v ∈ zero_forcing_boundary G (B ∪ W) → v ∉ W → v ∈ zero_forcing_boundary G B := by intro v hv hvnw rw [zero_forcing_boundary] at hv ⊢ rcases hv with ⟨hvBW, y, hy_adj, hy_notin⟩ have hvB : v ∈ B := by cases hvBW with | inl h => exact h | inr h => exact False.elim (hvnw h) refine ⟨hvB, y, hy_adj, fun hyB => hy_notin (Set.mem_union_left _ hyB)⟩ have h_maps : Set.MapsTo f (zero_forcing_boundary G (B ∪ W)) (zero_forcing_boundary G B) := by intro v hv by_cases hw : v ∈ W · rw [hf_W v hw] have hspec := Classical.choose_spec (hW v hw) exact h_in_boundary_of_W v (Classical.choose (hW v hw)) hspec.1 hspec.2 · rw [hf_not_W v hw] exact h_in_boundary_of_not_W v hv hw have h_inj : Set.InjOn f (zero_forcing_boundary G (B ∪ W)) := by intro u hu v hv heq by_cases huW : u ∈ W <;> by_cases hvW : v ∈ W · rw [hf_W u huW, hf_W v hvW] at heq have hu_spec := Classical.choose_spec (hW u huW) have hv_spec := Classical.choose_spec (hW v hvW) have h_eq_sets : ({u} : Set V) = {v} := by rw [← hu_spec.2, heq, hv_spec.2] exact Set.singleton_eq_singleton_iff.mp h_eq_sets · rw [hf_W u huW, hf_not_W v hvW] at heq have hu_spec := Classical.choose_spec (hW u huW) have h_u_notin := h_not_in_boundary u (Classical.choose (hW u huW)) hu_spec.1 hu_spec.2 rw [heq] at h_u_notin exact False.elim (h_u_notin hv) · rw [hf_not_W u huW, hf_W v hvW] at heq have hv_spec := Classical.choose_spec (hW v hvW) have h_v_notin := h_not_in_boundary v (Classical.choose (hW v hvW)) hv_spec.1 hv_spec.2 rw [← heq] at h_v_notin exact False.elim (h_v_notin hu) · rw [hf_not_W u huW, hf_not_W v hvW] at heq exact heq rw [hB'] exact Set.encard_le_encard_of_injOn h_maps h_inj