zero_forcing_root_exposed_unique_neighbor
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.
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.
intro v hv induction hv with | init v hvS => intro hvF exact hdisjoint v hvF hvS
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.
| 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 hxFAssume 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.
uses
Finset.union_subsetclassical by_contra hxy let K : Finset V := F ∪ H have hKW : K ⊆ W := Finset.union_subset hFW hHW
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.
uses
Finset.mem_sdiff.mphave 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)
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.
uses
Finset.mem_union_left,Finset.mem_union_right,Ne.symmhave 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⟩
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.
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⟩
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.
uses
fort_blocks,Finset.mem_union_leftexact (fort_blocks G ((Finset.univ \ W : Finset V) : Set V) (K : Set V) hdisjoint hfort x (hW x)) (Finset.mem_union_left H hx)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.
obtain ⟨F, hFW, hrF, ⟨x, hx, hrx⟩, hnear⟩ := hE refine ⟨x, ⟨hrx, F, hFW, hrF, hx, hnear⟩, ?_⟩
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.
uses
unique_exposed_neighborrintro 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
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 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