AFTD Auto-Formalizing Theoretical Domains

zero_forcing_root_exposed_unique_neighbor

theoremverified

If W is fort-free and contains a root-exposed fort, there is exactly one root neighbor belonging to any root-exposed fort contained in W.

Statement

theorem zero_forcing_root_exposed_unique_neighbor {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (r : V)
    (W : Finset V)
    (hW : is_zero_forcing_set G ((Finset.univ \ W : Finset V) : Set V))
    (hE : zero_forcing_root_exposed_fort G r W) :
    ∃! v : V, G.Adj r v ∧ ∃ F : Finset V, F ⊆ W ∧ r ∉ F ∧ v ∈ F ∧
      ∀ u : V, u ≠ r → u ∉ F → ∀ w : V, w ∈ F → G.Adj u w →
        ∃ x : V, x ∈ F ∧ G.Adj u x ∧ x ≠ w
Source
A fort-union observation for the rooted recurrence towards OP-1399, arXiv:2611.11352.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • zero_forcing_root_exposed_fortA white set W contains a root-exposed fort if it contains a set F not containing r such that r has a neighbor in F and every vertex other…
  • 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.

The proof, explained

To show that there is a unique neighbor of the root in any root-exposed fort contained in W, we first show that any fort disjoint from a zero forcing set cannot contain any forced vertices. We then prove that two root-exposed forts with distinct root neighbors would have their union form a full fort disjoint from the zero forcing set V \ W, which is impossible. Therefore, all root-exposed forts must share the same unique neighbor of the root.

  1. Vertices forced by S cannot belong to a disjoint fort F

    We proceed by induction on the definition of ZeroForced. In the base case, if v is initially in S, it cannot be in F since F and S are disjoint.

    lines 16–20

      intro v hv
      induction hv with
      | init v hvS =>
        intro hvF
        exact hdisjoint v hvF hvS
  2. The inductive step holds for zero forcing on a fort

    In the inductive step, if u forces w, u is not in F by the induction hypothesis. If w were in F, then because F is a fort, u would have another neighbor x in F distinct from w. But the forcing rule requires all other neighbors of u to be already forced, hence outside F by induction, giving a contradiction.

    lines 21–24

      | 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 hxF
  3. Assume x ≠ y and form the union K = F ∪ H ⊆ W

    Suppose for contradiction that x ≠ y. Let K be the union of F and H; since both are subsets of W, their union K is also a subset of W.

    lines 31–34

    uses Finset.union_subset

      classical
      by_contra hxy
      let K : Finset V := F ∪ H
      have hKW : K ⊆ W := Finset.union_subset hFW hHW
  4. K is disjoint from the complement of W

    Any element of K belongs to W, so it cannot belong to the complement Finset.univ \ W.

    lines 35–38

    uses Finset.mem_sdiff.mp

      have hdisjoint : ∀ z, z ∈ (K : Set V) →
          z ∉ ((Finset.univ \ W : Finset V) : Set V) := by
        intro z hzK hzS
        exact (Finset.mem_sdiff.mp hzS).2 (hKW hzK)
  5. K satisfies the fort condition for the root r

    If u = r and w is a neighbor of r in K, either w = x, in which case y ∈ H ⊆ K provides a distinct neighbor of r since x ≠ y, or w ≠ x, in which case x ∈ F ⊆ K provides a distinct neighbor.

    lines 39–47

    uses Finset.mem_union_left, Finset.mem_union_right, Ne.symm

      have hfort : ∀ u, u ∉ (K : Set V) → ∀ w, w ∈ (K : Set V) → G.Adj u w →
          ∃ z, z ∈ (K : Set V) ∧ G.Adj u z ∧ z ≠ w := by
        intro u hu w hw huw
        by_cases hur : u = r
        · subst u
          by_cases hwx : w = x
          · subst w
            exact ⟨y, Finset.mem_union_right F hy, hry, Ne.symm hxy⟩
          · exact ⟨x, Finset.mem_union_left H hx, hrx, Ne.symm hwx⟩
  6. K satisfies the fort condition for vertices u ≠ r

    If u ≠ r and u ∉ K, then u is neither in F nor in H. Any neighbor w of u in K belongs to F or H, so the near-fort property of that set provides another neighbor in K.

    lines 48–58

    uses Finset.mem_union_left, Finset.mem_union_right, Finset.mem_union.mp

        · have huF : u ∉ F := by
            intro huF
            exact hu (Finset.mem_union_left H huF)
          have huH : u ∉ H := by
            intro huH
            exact hu (Finset.mem_union_right F huH)
          rcases Finset.mem_union.mp hw with hwF | hwH
          · obtain ⟨z, hz, huz, hzw⟩ := hF.2 u hur huF w hwF huw
            exact ⟨z, Finset.mem_union_left H hz, huz, hzw⟩
          · obtain ⟨z, hz, huz, hzw⟩ := hH.2 u hur huH w hwH huw
            exact ⟨z, Finset.mem_union_right F hz, huz, hzw⟩
  7. K is a fort disjoint from the forcing set, reaching a contradiction

    By fort_blocks, no vertex in K can be forced by the complement of W. But the complement of W is a zero forcing set, so every vertex is forced, including x ∈ K, which is a contradiction. Thus x = y.

    lines 59–60

    uses fort_blocks, Finset.mem_union_left

      exact (fort_blocks G ((Finset.univ \ W : Finset V) : Set V) (K : Set V)
        hdisjoint hfort x (hW x)) (Finset.mem_union_left H hx)
  8. Extract a root-exposed fort and witness neighbor x

    From the assumption that W contains a root-exposed fort, we obtain a fort F ⊆ W and a neighbor x ∈ F of r, showing existence.

    lines 70–71

      obtain ⟨F, hFW, hrF, ⟨x, hx, hrx⟩, hnear⟩ := hE
      refine ⟨x, ⟨hrx, F, hFW, hrF, hx, hnear⟩, ?_⟩
  9. Uniqueness follows from unique_exposed_neighbor

    For any other neighbor y belonging to a root-exposed fort H ⊆ W, applying unique_exposed_neighbor shows x = y, so y = x.

    lines 72–74

    uses unique_exposed_neighbor

      rintro y ⟨hry, H, hHW, hrH, hy, hHnear⟩
      exact (unique_exposed_neighbor G r W F H hW hFW hHW ⟨hrF, hnear⟩
        ⟨hrH, hHnear⟩ x y hx hy hrx hry).symm
Finset.union_subset
If F and H are subsets of W, then their union is also a subset of W
Finset.mem_union_left
If an element is in F, it is in F ∪ H
Finset.mem_union_right
If an element is in H, it is in F ∪ H
Finset.mem_sdiff.mp
If an element is in a set difference A \ B, then it is in A and not in B
Finset.mem_union.mp
If an element is in F ∪ H, then it is in F or in H
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a
fort_blocks
No vertex of a fort disjoint from S can be forced by S
unique_exposed_neighbor
Any two root-exposed forts in W must have the same neighbor to the root

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

open SimpleGraphsectionvariable {V : Type*} [Fintype V] [DecidableEq V]variable (G : SimpleGraph V)private def near_fort (r : V) (F : Finset V) : Prop :=  r ∉ F ∧ ∀ u : V, u ≠ r → u ∉ F → ∀ w : V, w ∈ F → G.Adj u w →    ∃ x : V, x ∈ F ∧ G.Adj u x ∧ x ≠ wprivate theorem fort_blocks (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 hxFprivate theorem unique_exposed_neighbor (r : V) (W F H : Finset V)    (hW : is_zero_forcing_set G ((Finset.univ \ W : Finset V) : Set V))    (hFW : F ⊆ W) (hHW : H ⊆ W) (hF : near_fort G r F) (hH : near_fort G r H)    (x y : V) (hx : x ∈ F) (hy : y ∈ H) (hrx : G.Adj r x) (hry : G.Adj r y) :    x = y := by  classical  by_contra hxy  let K : Finset V := F ∪ H  have hKW : K ⊆ W := Finset.union_subset hFW hHW  have hdisjoint : ∀ z, z ∈ (K : Set V) →      z ∉ ((Finset.univ \ W : Finset V) : Set V) := by    intro z hzK hzS    exact (Finset.mem_sdiff.mp hzS).2 (hKW hzK)  have hfort : ∀ u, u ∉ (K : Set V) → ∀ w, w ∈ (K : Set V) → G.Adj u w →      ∃ z, z ∈ (K : Set V) ∧ G.Adj u z ∧ z ≠ w := by    intro u hu w hw huw    by_cases hur : u = r    · subst u      by_cases hwx : w = x      · subst w        exact ⟨y, Finset.mem_union_right F hy, hry, Ne.symm hxy⟩      · exact ⟨x, Finset.mem_union_left H hx, hrx, Ne.symm hwx⟩    · have huF : u ∉ F := by        intro huF        exact hu (Finset.mem_union_left H huF)      have huH : u ∉ H := by        intro huH        exact hu (Finset.mem_union_right F huH)      rcases Finset.mem_union.mp hw with hwF | hwH      · obtain ⟨z, hz, huz, hzw⟩ := hF.2 u hur huF w hwF huw        exact ⟨z, Finset.mem_union_left H hz, huz, hzw⟩      · obtain ⟨z, hz, huz, hzw⟩ := hH.2 u hur huH w hwH huw        exact ⟨z, Finset.mem_union_right F hz, huz, hzw⟩  exact (fort_blocks G ((Finset.univ \ W : Finset V) : Set V) (K : Set V)    hdisjoint hfort x (hW x)) (Finset.mem_union_left H hx)endtheorem zero_forcing_root_exposed_unique_neighbor {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (r : V)    (W : Finset V)    (hW : is_zero_forcing_set G ((Finset.univ \ W : Finset V) : Set V))    (hE : zero_forcing_root_exposed_fort G r W) :    ∃! v : V, G.Adj r v ∧ ∃ F : Finset V, F ⊆ W ∧ r ∉ F ∧ v ∈ F ∧      ∀ u : V, u ≠ r → u ∉ F → ∀ w : V, w ∈ F → G.Adj u w →        ∃ x : V, x ∈ F ∧ G.Adj u x ∧ x ≠ w := by  obtain ⟨F, hFW, hrF, ⟨x, hx, hrx⟩, hnear⟩ := hE  refine ⟨x, ⟨hrx, F, hFW, hrF, hx, hnear⟩, ?_⟩  rintro y ⟨hry, H, hHW, hrH, hy, hHnear⟩  exact (unique_exposed_neighbor G r W F H hW hFW hHW ⟨hrF, hnear⟩    ⟨hrH, hHnear⟩ x y hx hy hrx hry).symm
See it in the graphDiscuss this resultChallenge it