zero_forcing_pair_obstruction_transitive
For 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 transitive.
Statement
theorem zero_forcing_pair_obstruction_transitive {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (a b c : V) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (ha : is_zero_forcing_set G ((Finset.univ \ ({a} : Finset V) : Finset V) : Set V)) (hb : is_zero_forcing_set G ((Finset.univ \ ({b} : Finset V) : Finset V) : Set V)) (hc : is_zero_forcing_set G ((Finset.univ \ ({c} : Finset V) : Finset V) : Set V)) (hab_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,b} : Finset V) : Finset V) : Set V)) (hbc_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({b,c} : Finset V) : Finset V) : Set V)) : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,c} : Finset V) : Finset V) : Set V)
- Source
- Filed by the prover as a step towards another result
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- zfs_compl_iff_no_stuckFor 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.…
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
The proof, explained
The proof shows that for vertices whose individual singleton complements are zero forcing sets (i.e. fort-free white sets), a pair obstruction—where the complement of a two-vertex set fails to be zero forcing—is equivalent to the two vertices being twins (having identical neighborhoods outside the pair). A bad pair must be a twin because any fort in the pair cannot be contained in either singleton, forcing the pair itself to be a fort. Conversely, any pair of twins trivially satisfies the fort condition. The result then follows from the transitivity of the twin relation on distinct vertices.
There exists a nonempty fort F contained in {a, b}.
By `zfs_compl_iff_no_stuck`, the complement of a set T is a zero forcing set if and only if T contains no fort (a nonempty subset where every external neighbor has at least two neighbors in the subset). Since V \ {a, b} is assumed not to be zero forcing (`hbad`), by double-negation elimination (`Classical.not_not.mp`) there exists a nonempty fort F ⊆ {a, b}.
uses
zfs_compl_iff_no_stuck,Classical.not_not.mpclassical have hnot : ¬ ¬ ∃ F : Finset V, F.Nonempty ∧ F ⊆ ({a,b} : Finset V) ∧ (∀ u : V, u ∉ F → ∀ w : V, w ∈ F → G.Adj u w → ∃ x : V, x ∈ F ∧ G.Adj u x ∧ x ≠ w) := by intro h exact hbad ((zfs_compl_iff_no_stuck G ({a,b} : Finset V)).mpr h) obtain ⟨F, hne, hsub, hfort⟩ := Classical.not_not.mp hnot
Both a and b belong to the fort F.
Suppose for contradiction that a ∉ F. Because F ⊆ {a, b}, all elements of F must be either a or b; since a ∉ F, this implies F ⊆ {b}. But F is a fort, so this would mean {b} contains a fort, contradicting that V \ {b} is a zero forcing set (`hb`). Symmetrically, if b ∉ F then F ⊆ {a}, contradicting that V \ {a} is a zero forcing set (`ha`). Hence both a ∈ F and b ∈ F.
uses
zfs_compl_iff_no_stuckhave haF : a ∈ F := by by_contra haF have hFb : F ⊆ ({b} : Finset V) := by intro x hx have hx' : x = a ∨ x = b := by simpa using hsub hx rcases hx' with rfl | rfl · exact (haF hx).elim · simp exact ((zfs_compl_iff_no_stuck G ({b} : Finset V)).mp hb) ⟨F, hne, hFb, hfort⟩ have hbF : b ∈ F := by by_contra hbF have hFa : F ⊆ ({a} : Finset V) := by intro x hx have hx' : x = a ∨ x = b := by simpa using hsub hx rcases hx' with rfl | rfl · simp · exact (hbF hx).elim exact ((zfs_compl_iff_no_stuck G ({a} : Finset V)).mp ha) ⟨F, hne, hFa, hfort⟩
The fort F is exactly the pair {a, b}.
We have F ⊆ {a, b} by definition of F, and {a, b} ⊆ F because both a ∈ F and b ∈ F. By set antisymmetry (`Finset.Subset.antisymm`), F = {a, b}. Substituting this into the fort hypothesis shows that {a, b} itself is a fort.
uses
Finset.Subset.antisymm,Finset.insert_subset_iff,Finset.singleton_subset_iffhave hF : F = ({a,b} : Finset V) := by apply Finset.Subset.antisymm hsub simp only [Finset.insert_subset_iff, Finset.singleton_subset_iff] exact ⟨haF, hbF⟩ subst F
The vertices a and b are twins (`twin G a b`).
For any vertex u distinct from a and b (so u ∉ {a, b}), if u is adjacent to a, the fort condition for {a, b} provides an alternate neighbor x ∈ {a, b} of u with x ≠ a. The only element of {a, b} other than a is b, so u is adjacent to b. By symmetric reasoning, if u is adjacent to b, the fort condition implies u is adjacent to a. Thus u ~ a ↔ u ~ b, which means a and b are twins.
intro u hua hub have hu : u ∉ ({a,b} : Finset V) := by simp [hua, hub] constructor · intro h obtain ⟨x, hx, hux, hxa⟩ := hfort u hu a (by simp) h have hx' : x = b := by simpa [hxa] using hx simpa [hx'] using hux · intro h obtain ⟨x, hx, hux, hxb⟩ := hfort u hu b (by simp) h have hx' : x = a := by simpa [hxb] using hx simpa [hx'] using hux
Conversely, any pair of distinct twins forms an obstruction: V \ {a, b} is not a zero forcing set (`twin_bad_pair`).
By `zfs_compl_iff_no_stuck`, it suffices to show that {a, b} is a fort. For any vertex u ∉ {a, b} and any neighbor w ∈ {a, b} of u, w is either a or b. If w = a, the twin property implies u is also adjacent to b ≠ a. If w = b, the twin property implies u is also adjacent to a ≠ b. In either case, u has at least two neighbors in {a, b}, so {a, b} is a fort and V \ {a, b} cannot be a zero forcing set.
uses
zfs_compl_iff_no_stuck,Ne.symmintro hforce apply ((zfs_compl_iff_no_stuck G ({a,b} : Finset V)).mp hforce) refine ⟨{a,b}, by simp, by intro x hx; exact hx, ?_⟩ intro u hu w hw huw have hua : u ≠ a := by intro h'; apply hu; simp [h'] have hub : u ≠ b := by intro h'; apply hu; simp [h'] have hw' : w = a ∨ w = b := by simpa using hw rcases hw' with rfl | rfl · exact ⟨b, by simp, (h u hua hub).mp huw, Ne.symm hab⟩ · exact ⟨a, by simp, (h u hua hub).mpr huw, hab⟩
The twin relation is transitive on triples of distinct vertices (`twin_trans`).
Let a, b, c be pairwise distinct vertices with a, b twins and b, c twins. For any vertex u ≠ a, c, we must show u ~ a ↔ u ~ c. If u ≠ b, this follows by transitivity of equivalence from u ~ a ↔ u ~ b and u ~ b ↔ u ~ c. If u = b, we must show b ~ a ↔ b ~ c. Since b, c are twins and a ≠ b, c, we have a ~ b ↔ a ~ c. Since a, b are twins and c ≠ a, b, we have c ~ a ↔ c ~ b. By symmetry of adjacency in SimpleGraph, b ~ a ↔ a ~ b ↔ a ~ c ↔ c ~ a ↔ c ~ b ↔ b ~ c. Hence a, c are twins in all cases.
uses
Ne.symmintro u hua huc by_cases hub : u = b · subst u have h1 : G.Adj a b ↔ G.Adj a c := hbcT a hab hac have h2 : G.Adj c a ↔ G.Adj c b := habT c (Ne.symm hac) (Ne.symm hbc) constructor · intro hba have hab' : G.Adj a b := hba.symm have hac' : G.Adj a c := h1.mp hab' have hca : G.Adj c a := hac'.symm have hcb : G.Adj c b := h2.mp hca exact hcb.symm · intro hbc' have hcb : G.Adj c b := hbc'.symm have hca : G.Adj c a := h2.mpr hcb have hac' : G.Adj a c := hca.symm have hab' : G.Adj a b := h1.mpr hac' exact hab'.symm · exact (habT u hua hub).trans (hbcT u hub huc)
For vertices with fort-free singletons, the two-vertex obstruction relation is transitive (`transitive`).
Assuming V \ {a}, V \ {b}, and V \ {c} are zero forcing sets, while V \ {a, b} and V \ {b, c} are not: by `bad_pair_is_twin`, a and b are twins, and b and c are twins. By `twin_trans`, a and c are twins. Finally, by `twin_bad_pair`, V \ {a, c} is not a zero forcing set.
uses
twin_bad_pair,twin_trans,bad_pair_is_twinexact twin_bad_pair G a c hac (twin_trans G a b c hab hbc hac (bad_pair_is_twin G a b hab ha hb hab_bad) (bad_pair_is_twin G b c hbc hb hc hbc_bad))Theorem `zero_forcing_pair_obstruction_transitive` holds.
The main theorem is identical to `IN800PairObstruction.transitive` outside the namespace; we conclude by directly applying `IN800PairObstruction.transitive`.
uses
IN800PairObstruction.transitiveexact IN800PairObstruction.transitive G a b c hab hbc hac ha hb hc hab_bad hbc_bad
zfs_compl_iff_no_stuck- A set's complement is a zero forcing set if and only if the set contains no fort (stuck set).
Classical.not_not.mp- Double negation elimination: ¬¬P implies P.
Finset.Subset.antisymm- Two finite sets are equal if each is a subset of the other.
Finset.insert_subset_iff- insert a s ⊆ t if and only if a ∈ t and s ⊆ t.
Finset.singleton_subset_iff- A singleton set {a} is a subset of s if and only if a ∈ s.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
bad_pair_is_twin- If two distinct vertices have fort-free singleton complements but their two-vertex complement is not zero forcing, then they are twins.
twin_bad_pair- If two distinct vertices are twins, then their two-vertex complement is not a zero forcing set (it contains a fort).
twin_trans- The twin relation is transitive on triples of distinct vertices.
IN800PairObstruction.transitive- Transitivity of the pair obstruction property for vertices with fort-free singletons.
- The Lean formalization works with SimpleGraph, where adjacency is an irreflexive, symmetric relation. Adjacency symmetry is invoked on hypotheses (e.g. `hba.symm`), while classical logic (`Classical.not_not.mp`) is used to extract the fort witness from the assumption that a set is not zero forcing.
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.
set_option maxRecDepth 8192set_option maxHeartbeats 8000000namespace IN800PairObstructionvariable {V : Type*} [Fintype V] [DecidableEq V]def twin (G : SimpleGraph V) (a b : V) : Prop := ∀ u : V, u ≠ a → u ≠ b → (G.Adj u a ↔ G.Adj u b)lemma bad_pair_is_twin (G : SimpleGraph V) (a b : V) (hab : a ≠ b) (ha : is_zero_forcing_set G ((Finset.univ \ ({a} : Finset V) : Finset V) : Set V)) (hb : is_zero_forcing_set G ((Finset.univ \ ({b} : Finset V) : Finset V) : Set V)) (hbad : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,b} : Finset V) : Finset V) : Set V)) : twin G a b := by classical have hnot : ¬ ¬ ∃ F : Finset V, F.Nonempty ∧ F ⊆ ({a,b} : Finset V) ∧ (∀ u : V, u ∉ F → ∀ w : V, w ∈ F → G.Adj u w → ∃ x : V, x ∈ F ∧ G.Adj u x ∧ x ≠ w) := by intro h exact hbad ((zfs_compl_iff_no_stuck G ({a,b} : Finset V)).mpr h) obtain ⟨F, hne, hsub, hfort⟩ := Classical.not_not.mp hnot have haF : a ∈ F := by by_contra haF have hFb : F ⊆ ({b} : Finset V) := by intro x hx have hx' : x = a ∨ x = b := by simpa using hsub hx rcases hx' with rfl | rfl · exact (haF hx).elim · simp exact ((zfs_compl_iff_no_stuck G ({b} : Finset V)).mp hb) ⟨F, hne, hFb, hfort⟩ have hbF : b ∈ F := by by_contra hbF have hFa : F ⊆ ({a} : Finset V) := by intro x hx have hx' : x = a ∨ x = b := by simpa using hsub hx rcases hx' with rfl | rfl · simp · exact (hbF hx).elim exact ((zfs_compl_iff_no_stuck G ({a} : Finset V)).mp ha) ⟨F, hne, hFa, hfort⟩ have hF : F = ({a,b} : Finset V) := by apply Finset.Subset.antisymm hsub simp only [Finset.insert_subset_iff, Finset.singleton_subset_iff] exact ⟨haF, hbF⟩ subst F intro u hua hub have hu : u ∉ ({a,b} : Finset V) := by simp [hua, hub] constructor · intro h obtain ⟨x, hx, hux, hxa⟩ := hfort u hu a (by simp) h have hx' : x = b := by simpa [hxa] using hx simpa [hx'] using hux · intro h obtain ⟨x, hx, hux, hxb⟩ := hfort u hu b (by simp) h have hx' : x = a := by simpa [hxb] using hx simpa [hx'] using huxlemma twin_bad_pair (G : SimpleGraph V) (a b : V) (hab : a ≠ b) (h : twin G a b) : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,b} : Finset V) : Finset V) : Set V) := by intro hforce apply ((zfs_compl_iff_no_stuck G ({a,b} : Finset V)).mp hforce) refine ⟨{a,b}, by simp, by intro x hx; exact hx, ?_⟩ intro u hu w hw huw have hua : u ≠ a := by intro h'; apply hu; simp [h'] have hub : u ≠ b := by intro h'; apply hu; simp [h'] have hw' : w = a ∨ w = b := by simpa using hw rcases hw' with rfl | rfl · exact ⟨b, by simp, (h u hua hub).mp huw, Ne.symm hab⟩ · exact ⟨a, by simp, (h u hua hub).mpr huw, hab⟩lemma twin_trans (G : SimpleGraph V) (a b c : V) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (habT : twin G a b) (hbcT : twin G b c) : twin G a c := by intro u hua huc by_cases hub : u = b · subst u have h1 : G.Adj a b ↔ G.Adj a c := hbcT a hab hac have h2 : G.Adj c a ↔ G.Adj c b := habT c (Ne.symm hac) (Ne.symm hbc) constructor · intro hba have hab' : G.Adj a b := hba.symm have hac' : G.Adj a c := h1.mp hab' have hca : G.Adj c a := hac'.symm have hcb : G.Adj c b := h2.mp hca exact hcb.symm · intro hbc' have hcb : G.Adj c b := hbc'.symm have hca : G.Adj c a := h2.mpr hcb have hac' : G.Adj a c := hca.symm have hab' : G.Adj a b := h1.mpr hac' exact hab'.symm · exact (habT u hua hub).trans (hbcT u hub huc)theorem transitive (G : SimpleGraph V) (a b c : V) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (ha : is_zero_forcing_set G ((Finset.univ \ ({a} : Finset V) : Finset V) : Set V)) (hb : is_zero_forcing_set G ((Finset.univ \ ({b} : Finset V) : Finset V) : Set V)) (hc : is_zero_forcing_set G ((Finset.univ \ ({c} : Finset V) : Finset V) : Set V)) (hab_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,b} : Finset V) : Finset V) : Set V)) (hbc_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({b,c} : Finset V) : Finset V) : Set V)) : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,c} : Finset V) : Finset V) : Set V) := by exact twin_bad_pair G a c hac (twin_trans G a b c hab hbc hac (bad_pair_is_twin G a b hab ha hb hab_bad) (bad_pair_is_twin G b c hbc hb hc hbc_bad))end IN800PairObstructiontheorem zero_forcing_pair_obstruction_transitive {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (a b c : V) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (ha : is_zero_forcing_set G ((Finset.univ \ ({a} : Finset V) : Finset V) : Set V)) (hb : is_zero_forcing_set G ((Finset.univ \ ({b} : Finset V) : Finset V) : Set V)) (hc : is_zero_forcing_set G ((Finset.univ \ ({c} : Finset V) : Finset V) : Set V)) (hab_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,b} : Finset V) : Finset V) : Set V)) (hbc_bad : ¬ is_zero_forcing_set G ((Finset.univ \ ({b,c} : Finset V) : Finset V) : Set V)) : ¬ is_zero_forcing_set G ((Finset.univ \ ({a,c} : Finset V) : Finset V) : Set V) := by exact IN800PairObstruction.transitive G a b c hab hbc hac ha hb hc hab_bad hbc_bad