AFTD Auto-Formalizing Theoretical Domains

zero_forcing_pair_obstruction_transitive

theoremverified

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.

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

    lines 16–22

    uses zfs_compl_iff_no_stuck, Classical.not_not.mp

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

    lines 23–40

    uses zfs_compl_iff_no_stuck

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

    lines 41–45

    uses Finset.Subset.antisymm, Finset.insert_subset_iff, Finset.singleton_subset_iff

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

    lines 46–56

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

    lines 60–69

    uses zfs_compl_iff_no_stuck, Ne.symm

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

    lines 74–92

    uses Ne.symm

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

    lines 101–103

    uses twin_bad_pair, twin_trans, bad_pair_is_twin

      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))
  8. 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`.

    line 108

    uses IN800PairObstruction.transitive

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

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

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