AFTD Auto-Formalizing Theoretical Domains

zero_forcing_boundary_mono

theoremverifiedformalization

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.

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

    lines 3–13

    uses dif_pos, dif_neg

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

    lines 14–24

    uses Set.mem_union_left, Set.mem_singleton_iff, Set.mem_union_right

      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⟩)
    
  3. 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.

    lines 25–34

    uses Set.mem_singleton

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

    lines 35–45

    uses False.elim, Set.mem_union_left

      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)⟩
    
  5. 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.

    lines 46–54

    uses Classical.choose_spec

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

    lines 55–76

    uses Classical.choose_spec, Set.singleton_eq_singleton_iff.mp, False.elim

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

    lines 77–78

    uses Set.encard_le_encard_of_injOn

      rw [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.

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

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