AFTD Auto-Formalizing Theoretical Domains

tree_zero_forcing_complements_not_two_extendible

theoremverifiedoriginal

There is a tree on nine vertices whose complements of zero forcing sets are not two-extendible.

Statement

theorem tree_zero_forcing_complements_not_two_extendible : ∃ G : SimpleGraph (Fin 9), G.IsTree ∧ ¬ zero_forcing_complements_two_extendible G
Related work
A computationally discovered obstruction to using intersection-of-two-matroids for OP-1399. The two-matroid independent-set coefficient result is described in arXiv:2608.23262.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • zero_forcing_complements_two_extendibleComplements of zero forcing sets have the two-extendibility property: whenever A is contained in B, x is outside B, and A, B and A union…
  • 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.
  • Arena.Reachable.transReachability is transitive.

Read back from the Lean

There exists a simple graph $G$ on the vertex type Fin 9 such that: 1. $G$ is a tree (G.IsTree), and 2. $G$ does not satisfy zero_forcing_complements_two_extendible, which means it is NOT the case that: for all finite vertex subsets $A, B \subseteq \text{Fin } 9$ satisfying $A \subseteq B$, if the complement $\text{Fin } 9 \setminus A$ is a zero forcing set of $G$, and the complement $\text{Fin } 9 \setminus B$ is a zero forcing set of $G$, then for all vertices $x \in \text{Fin } 9$ with $x \notin B$, if the complement $\text{Fin } 9 \setminus (A \cup \{x\})$ is a zero forcing set of $G$, then there exists a subset $R \subseteq B \setminus A$ with $|R| \le 2$ such that the complement $\text{Fin } 9 \setminus ((B \setminus R) \cup \{x\})$ is a zero forcing set of $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

The theorem is proved by exhibiting an explicit 9-vertex tree and showing that its zero forcing complements fail 2-extendibility. Two nested sets of vertices A ⊂ B with |B \ A| = 3 and an external vertex x = 8 are chosen so that the complements V \ A, V \ B, and V \ (A ∪ {x}) are all zero forcing sets. To disprove 2-extendibility, it is shown that no repair set R ⊆ B \ A of size at most 2 can make the complement of (B \ R) ∪ {x} zero forcing. This is established using fort theory: in all seven candidate cases for R, the target set contains a nonempty fort, obstructing zero forcing on the complement.

  1. The 9-vertex graph `witness_graph` is a well-defined, loopless, undirected simple graph with decidable adjacency.

    The graph is defined on vertices {0, ..., 8} as the symmetric closure of 8 edges: (0,1), (1,2), (0,5), (2,3), (3,4), (5,6), (5,8), and (6,7). Symmetry holds by swapping pairs, looplessness is verified by exhaustive check over all 9 vertices, and decidability of adjacency follows from the finiteness of the edge list.

    lines 1–15

    open SimpleGraph
    
    private def witness_edges : List (Fin 9 × Fin 9) :=
      [(0, 1), (1, 2), (0, 5), (2, 3), (3, 4), (5, 6), (5, 8), (6, 7)]
    
    private def witness_graph : SimpleGraph (Fin 9) where
      Adj u v := (u, v) ∈ witness_edges ∨ (v, u) ∈ witness_edges
      symm := ⟨by intro u v h; exact h.symm⟩
      loopless := ⟨by intro v; fin_cases v <;> decide⟩
    
    private instance : DecidableRel witness_graph.Adj := by
      intro u v
      change Decidable ((u, v) ∈ witness_edges ∨ (v, u) ∈ witness_edges)
      infer_instance
    
  2. `witness_graph` is a tree.

    A finite graph is a tree if it is connected and |E| + 1 = |V| (by `SimpleGraph.isTree_iff_connected_and_card.mpr`). Connectivity is shown by exhibiting paths from vertex 0 to every other vertex: 0 connects directly to 1 and 5, which chain to 2, 3, 4, 6, 7, and 8. The edge count condition 8 + 1 = 9 is verified by computation after converting cardinality using `Nat.card_eq_fintype_card`.

    lines 16–42

    uses SimpleGraph.isTree_iff_connected_and_card.mpr, SimpleGraph.Reachable.rfl, Nat.card_eq_fintype_card

    private theorem witness_tree : witness_graph.IsTree := by
      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
      · apply (witness_graph.connected_iff_exists_forall_reachable).mpr
        refine ⟨0, ?_⟩
        have h01 : witness_graph.Reachable 0 1 := (show witness_graph.Adj 0 1 by decide).reachable
        have h02 : witness_graph.Reachable 0 2 := h01.trans (show witness_graph.Adj 1 2 by decide).reachable
        have h03 : witness_graph.Reachable 0 3 := h02.trans (show witness_graph.Adj 2 3 by decide).reachable
        have h04 : witness_graph.Reachable 0 4 := h03.trans (show witness_graph.Adj 3 4 by decide).reachable
        have h05 : witness_graph.Reachable 0 5 := (show witness_graph.Adj 0 5 by decide).reachable
        have h06 : witness_graph.Reachable 0 6 := h05.trans (show witness_graph.Adj 5 6 by decide).reachable
        have h07 : witness_graph.Reachable 0 7 := h06.trans (show witness_graph.Adj 6 7 by decide).reachable
        have h08 : witness_graph.Reachable 0 8 := h05.trans (show witness_graph.Adj 5 8 by decide).reachable
        intro v
        fin_cases v
        · exact SimpleGraph.Reachable.rfl
        · exact h01
        · exact h02
        · exact h03
        · exact h04
        · exact h05
        · exact h06
        · exact h07
        · exact h08
      · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]
        decide
    
  3. The set `blue_a` = {0, 2, 3, 6} is a zero forcing set in `witness_graph`.

    Vertices 0, 2, 3, 6 are initially in the set. Then vertex 2 forces neighbor 1 (neighbor 3 is already in the set); vertex 0 forces 5 (neighbor 1 is now forced); vertex 3 forces 4 (neighbor 2 is forced); vertex 5 forces 8 (neighbors 0 and 6 are forced); and vertex 6 forces 7 (neighbor 5 is forced). This completes the forcing of all 9 vertices.

    lines 43–73

    uses ZeroForced.init, ZeroForced.step

    private def blue_a : Set (Fin 9) := {0, 2, 3, 6}
    private def blue_b : Set (Fin 9) := {0, 8}
    
    private theorem blue_a_forcing : is_zero_forcing_set witness_graph blue_a := by
      have h0 : ZeroForced witness_graph blue_a 0 := ZeroForced.init 0 (by simp [blue_a])
      have h2 : ZeroForced witness_graph blue_a 2 := ZeroForced.init 2 (by simp [blue_a])
      have h3 : ZeroForced witness_graph blue_a 3 := ZeroForced.init 3 (by simp [blue_a])
      have h6 : ZeroForced witness_graph blue_a 6 := ZeroForced.init 6 (by simp [blue_a])
      have h1 : ZeroForced witness_graph blue_a 1 := by
        apply ZeroForced.step 2 1 h2 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h5 : ZeroForced witness_graph blue_a 5 := by
        apply ZeroForced.step 0 5 h0 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h4 : ZeroForced witness_graph blue_a 4 := by
        apply ZeroForced.step 3 4 h3 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h8 : ZeroForced witness_graph blue_a 8 := by
        apply ZeroForced.step 5 8 h5 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h7 : ZeroForced witness_graph blue_a 7 := by
        apply ZeroForced.step 6 7 h6 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      intro v
      fin_cases v <;> assumption
    
  4. The set `blue_b` = {0, 8} is a zero forcing set in `witness_graph`.

    Starting from {0, 8}, vertex 8 forces 5; vertex 0 forces 1; vertex 1 forces 2; vertex 2 forces 3; vertex 3 forces 4; vertex 5 forces 6; and vertex 6 forces 7. All 9 vertices are thereby forced.

    lines 74–107

    uses ZeroForced.init, ZeroForced.step

    private theorem blue_b_forcing : is_zero_forcing_set witness_graph blue_b := by
      have h0 : ZeroForced witness_graph blue_b 0 := ZeroForced.init 0 (by simp [blue_b])
      have h8 : ZeroForced witness_graph blue_b 8 := ZeroForced.init 8 (by simp [blue_b])
      have h5 : ZeroForced witness_graph blue_b 5 := by
        apply ZeroForced.step 8 5 h8 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h1 : ZeroForced witness_graph blue_b 1 := by
        apply ZeroForced.step 0 1 h0 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h2 : ZeroForced witness_graph blue_b 2 := by
        apply ZeroForced.step 1 2 h1 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h3 : ZeroForced witness_graph blue_b 3 := by
        apply ZeroForced.step 2 3 h2 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h4 : ZeroForced witness_graph blue_b 4 := by
        apply ZeroForced.step 3 4 h3 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h6 : ZeroForced witness_graph blue_b 6 := by
        apply ZeroForced.step 5 6 h5 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      have h7 : ZeroForced witness_graph blue_b 7 := by
        apply ZeroForced.step 6 7 h6 (by decide)
        intro v hv hne
        fin_cases v <;> simp_all [witness_graph, witness_edges]
      intro v
      fin_cases v <;> assumption
    
  5. If a fort F is disjoint from a set S, then zero forcing starting from S can never force any vertex in F (`fort_blocking`).

    By definition, a fort F is a set where any outside vertex with a neighbor in F has at least two neighbors in F. We proceed by induction on the zero forcing derivation. Initial vertices in S cannot be in F by disjointness. If an outside vertex u were to force w ∈ F, u would need w to be its unique unforced neighbor; but the fort property guarantees another neighbor x ∈ F distinct from w, which by the induction hypothesis cannot yet be forced, preventing u from forcing w.

    lines 108–122

    private theorem fort_blocking {V : Type*} (G : SimpleGraph V) (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 hxF
    
  6. If a vertex set W contains a nonempty fort F, then its complement V \ W is not a zero forcing set (`fort_blocks_complement`).

    Since F ⊆ W, F is disjoint from V \ W (by `Finset.mem_sdiff.mp`). By `fort_blocking`, no vertex in F can ever be forced from V \ W. Because F is nonempty, at least one vertex remains unforced, so V \ W cannot be a zero forcing set.

    lines 123–136

    uses Finset.mem_sdiff.mp, fort_blocking

    private theorem fort_blocks_complement {V : Type*} [Fintype V] [DecidableEq V]
        (G : SimpleGraph V) (W F : Finset V) (hsub : F ⊆ W) (hne : F.Nonempty)
        (hfort : ∀ u, u ∉ F → ∀ w, w ∈ F → G.Adj u w →
          ∃ x, x ∈ F ∧ G.Adj u x ∧ x ≠ w) :
        ¬ is_zero_forcing_set G ((Finset.univ \ W : Finset V) : Set V) := by
      intro hS
      obtain ⟨v, hv⟩ := hne
      have hdisj : ∀ v, v ∈ (F : Set V) → v ∉ ((Finset.univ \ W : Finset V) : Set V) := by
        intro x hxF hxS
        exact (Finset.mem_sdiff.mp hxS).2 (hsub hxF)
      have hf : ∀ u, u ∉ (F : Set V) → ∀ w, w ∈ (F : Set V) → G.Adj u w →
          ∃ x, x ∈ (F : Set V) ∧ G.Adj u x ∧ x ≠ w := hfort
      exact fort_blocking G ((Finset.univ \ W : Finset V) : Set V) (F : Set V) hdisj hf v (hS v) hv
    
  7. Zero forcing is monotone under set inclusion (`forced_mono`).

    If S ⊆ T, any vertex forced from S is also forced from T. This is proven by induction on the forcing derivation: initial vertices of S belong to T, and each forcing step remains valid for the larger set.

    lines 137–147

    uses ZeroForced.init, ZeroForced.step

    private theorem forced_mono {V : Type*} (G : SimpleGraph V) {S T : Set V} (h : S ⊆ T) :
        ∀ v, ZeroForced G S v → ZeroForced G T v := by
      intro v hv
      induction hv with
      | init v hvS => exact ZeroForced.init v (h hvS)
      | step u w hu huw hothers ihu ihothers =>
        exact ZeroForced.step u w ihu huw ihothers
    
    private def white_A : Finset (Fin 9) := {1, 4, 5, 7}
    private def white_B : Finset (Fin 9) := {1, 2, 3, 4, 5, 6, 7}
    
  8. For A = {1, 4, 5, 7} and B = {1, 2, 3, 4, 5, 6, 7}, the complements V \ (A ∪ {8}), V \ B, and V \ A are all zero forcing sets.

    The complement V \ (A ∪ {8}) equals `blue_a`, which is forcing by `blue_a_forcing`. The complement V \ B equals `blue_b`, which is forcing by `blue_b_forcing`. Since V \ (A ∪ {8}) ⊆ V \ A (checked via `Finset.mem_sdiff.mp`, `Finset.mem_sdiff.mpr`, `Finset.mem_univ`, and `Finset.mem_insert_of_mem`), monotonicity (`forced_mono`) implies V \ A is also a zero forcing set (`blue_A_forcing`).

    lines 148–172

    uses blue_a_forcing, blue_b_forcing, forced_mono, blue_A_insert_forcing, Finset.mem_univ, Finset.mem_insert_of_mem, Finset.mem_sdiff.mp, Finset.mem_sdiff.mpr

    private theorem blue_A_insert_forcing :
        is_zero_forcing_set witness_graph
          ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)) := by
      have hset : ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)) = blue_a := by
        ext v
        fin_cases v <;> simp [white_A, blue_a]
      rw [hset]
      exact blue_a_forcing
    
    private theorem blue_B_forcing :
        is_zero_forcing_set witness_graph ((Finset.univ \ white_B : Finset (Fin 9)) : Set (Fin 9)) := by
      have hset : ((Finset.univ \ white_B : Finset (Fin 9)) : Set (Fin 9)) = blue_b := by
        ext v
        fin_cases v <;> simp [white_B, blue_b]
      rw [hset]
      exact blue_b_forcing
    
    private theorem blue_A_forcing :
        is_zero_forcing_set witness_graph ((Finset.univ \ white_A : Finset (Fin 9)) : Set (Fin 9)) := by
      intro v
      apply forced_mono witness_graph (S := ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)))
      · intro x hx
        exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, fun hxA => (Finset.mem_sdiff.mp hx).2 (Finset.mem_insert_of_mem hxA)⟩
      · exact blue_A_insert_forcing v
    
  9. No candidate repair set R ⊆ B \ A of size |R| ≤ 2 yields a zero forcing complement for (B \ R) ∪ {8} (`no_two_repairs`).

    The difference B \ A is {2, 3, 6}, which has 3 elements. Since |R| ≤ 2, R cannot be all three elements (by `Finset.card_le_card`). Case analysis on the membership of 2, 3, 6 in R leaves 7 cases. In each case, (B \ R) ∪ {8} contains a nonempty fort: {6, 7, 8}, {1, 3, 4, 5, 7, 8}, {1, 3, 4, 5, 6, 7, 8}, {1, 2, 4, 5, 7, 8}, {1, 2, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 7, 8}, or {1, 2, 3, 4, 5, 6, 7, 8}. In each case, `fort_blocks_complement` concludes that the complement is not zero forcing.

    lines 173–227

    uses Finset.card_le_card, fort_blocks_complement

    private theorem no_two_repairs (R : Finset (Fin 9)) (hR : R ⊆ white_B \ white_A)
        (hcard : R.card ≤ 2) :
        ¬ is_zero_forcing_set witness_graph
          ((Finset.univ \ insert 8 (white_B \ R) : Finset (Fin 9)) : Set (Fin 9)) := by
      have hBA : white_B \ white_A = ({2, 3, 6} : Finset (Fin 9)) := by decide
      have hsub : R ⊆ ({2, 3, 6} : Finset (Fin 9)) := by simpa only [hBA] using hR
      have h1 : (1 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh
      have h4 : (4 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh
      have h5 : (5 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh
      have h7 : (7 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh
      by_cases h2 : (2 : Fin 9) ∈ R <;> by_cases h3 : (3 : Fin 9) ∈ R <;> by_cases h6 : (6 : Fin 9) ∈ R
      · have hthree : ({2, 3, 6} : Finset (Fin 9)) ⊆ R := by
          intro x hx
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          rcases hx with rfl | rfl | rfl <;> assumption
        have hc := Finset.card_le_card hthree
        have hcard3 : ({2, 3, 6} : Finset (Fin 9)).card = 3 := by decide
        rw [hcard3] at hc
        omega
      · apply fort_blocks_complement witness_graph _ ({6, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 3, 4, 5, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 3, 4, 5, 6, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 2, 4, 5, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 2, 4, 5, 6, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 2, 3, 4, 5, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
      · apply fort_blocks_complement witness_graph _ ({1, 2, 3, 4, 5, 6, 7, 8} : Finset (Fin 9))
        · intro x hx
          fin_cases x <;> simp_all [white_B]
        · decide
        · decide
    
  10. `witness_graph` does not have 2-extendible zero forcing complements (`witness_not_two_extendible`).

    Suppose for contradiction that zero forcing complements were 2-extendible. Applying this to A = {1, 4, 5, 7}, B = {1, 2, 3, 4, 5, 6, 7}, and x = 8 satisfies all hypotheses (A ⊆ B, 8 ∉ B, and V \ A, V \ B, and V \ (A ∪ {8}) are forcing via `blue_A_forcing`, `blue_B_forcing`, and `blue_A_insert_forcing`). This would produce a repair R ⊆ B \ A with |R| ≤ 2 whose complement is forcing, contradicting `no_two_repairs`.

    lines 228–241

    uses blue_A_forcing, blue_B_forcing, blue_A_insert_forcing, no_two_repairs

    private theorem witness_not_two_extendible :
        ¬ (∀ A B : Finset (Fin 9), A ⊆ B →
          is_zero_forcing_set witness_graph ((Finset.univ \ A : Finset (Fin 9)) : Set (Fin 9)) →
          is_zero_forcing_set witness_graph ((Finset.univ \ B : Finset (Fin 9)) : Set (Fin 9)) →
          ∀ x : Fin 9, x ∉ B →
          is_zero_forcing_set witness_graph ((Finset.univ \ insert x A : Finset (Fin 9)) : Set (Fin 9)) →
          ∃ R : Finset (Fin 9), R ⊆ B \ A ∧ R.card ≤ 2 ∧
            is_zero_forcing_set witness_graph ((Finset.univ \ insert x (B \ R) : Finset (Fin 9)) : Set (Fin 9))) := by
      intro h
      have hab : white_A ⊆ white_B := by decide
      have hx : (8 : Fin 9) ∉ white_B := by decide
      obtain ⟨R, hR, hc, hforce⟩ := h white_A white_B hab blue_A_forcing blue_B_forcing 8 hx blue_A_insert_forcing
      exact no_two_repairs R hR hc hforce
    
  11. There exists a tree on 9 vertices whose zero forcing complements are not 2-extendible.

    The theorem is concluded by providing `witness_graph` as the witness, pairing it with `witness_tree` proving it is a tree and `witness_not_two_extendible` proving that its zero forcing complements are not 2-extendible.

    lines 242–243

    uses witness_tree, witness_not_two_extendible

    theorem tree_zero_forcing_complements_not_two_extendible : ∃ G : SimpleGraph (Fin 9), G.IsTree ∧ ¬ zero_forcing_complements_two_extendible G := by
      exact ⟨witness_graph, witness_tree, witness_not_two_extendible⟩
SimpleGraph.isTree_iff_connected_and_card.mpr
A finite graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices.
SimpleGraph.Reachable.rfl
Every vertex is reachable from itself in zero steps.
Nat.card_eq_fintype_card
The natural-number cardinality of a finite type equals its Fintype cardinality.
ZeroForced.init
Any vertex in the initial set is zero forced.
ZeroForced.step
If an already zero-forced vertex has exactly one unforced neighbor, that neighbor becomes zero forced.
Finset.mem_sdiff.mp
If an element belongs to a set difference s \ t, then it belongs to s and does not belong to t.
fort_blocking
If a fort is disjoint from a set S, then zero forcing starting from S can never force any vertex in the fort.
blue_a_forcing
The set blue_a = {0, 2, 3, 6} is a zero forcing set in witness_graph.
blue_b_forcing
The set blue_b = {0, 8} is a zero forcing set in witness_graph.
forced_mono
Zero forcing is monotone under set inclusion: if S ⊆ T, any vertex forced by S is also forced by T.
blue_A_insert_forcing
The complement V \ (A ∪ {8}) is a zero forcing set in witness_graph.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.mem_insert_of_mem
If an element belongs to a finset, it also belongs to the finset with another element inserted.
Finset.mem_sdiff.mpr
If an element belongs to s and does not belong to t, then it belongs to s \ t.
Finset.card_le_card
A subset of a finset has cardinality less than or equal to the superset.
fort_blocks_complement
If a vertex set W contains a nonempty fort, then its complement V \ W cannot be a zero forcing set.
blue_A_forcing
The complement V \ A is a zero forcing set in witness_graph.
blue_B_forcing
The complement V \ B is a zero forcing set in witness_graph.
no_two_repairs
No subset R ⊆ B \ A of size at most 2 yields a zero forcing complement for (B \ R) ∪ {8}.
witness_tree
witness_graph is a tree.
witness_not_two_extendible
witness_graph does not have 2-extendible zero forcing complements.

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

Lean’s trace was cut to the first 400 of 447 tactics.

open SimpleGraphprivate def witness_edges : List (Fin 9 × Fin 9) :=  [(0, 1), (1, 2), (0, 5), (2, 3), (3, 4), (5, 6), (5, 8), (6, 7)]private def witness_graph : SimpleGraph (Fin 9) where  Adj u v := (u, v) ∈ witness_edges ∨ (v, u) ∈ witness_edges  symm := ⟨by intro u v h; exact h.symm⟩  loopless := ⟨by intro v; fin_cases v <;> decide⟩private instance : DecidableRel witness_graph.Adj := by  intro u v  change Decidable ((u, v) ∈ witness_edges ∨ (v, u) ∈ witness_edges)  infer_instanceprivate theorem witness_tree : witness_graph.IsTree := by  apply SimpleGraph.isTree_iff_connected_and_card.mpr  constructor  · apply (witness_graph.connected_iff_exists_forall_reachable).mpr    refine ⟨0, ?_⟩    have h01 : witness_graph.Reachable 0 1 := (show witness_graph.Adj 0 1 by decide).reachable    have h02 : witness_graph.Reachable 0 2 := h01.trans (show witness_graph.Adj 1 2 by decide).reachable    have h03 : witness_graph.Reachable 0 3 := h02.trans (show witness_graph.Adj 2 3 by decide).reachable    have h04 : witness_graph.Reachable 0 4 := h03.trans (show witness_graph.Adj 3 4 by decide).reachable    have h05 : witness_graph.Reachable 0 5 := (show witness_graph.Adj 0 5 by decide).reachable    have h06 : witness_graph.Reachable 0 6 := h05.trans (show witness_graph.Adj 5 6 by decide).reachable    have h07 : witness_graph.Reachable 0 7 := h06.trans (show witness_graph.Adj 6 7 by decide).reachable    have h08 : witness_graph.Reachable 0 8 := h05.trans (show witness_graph.Adj 5 8 by decide).reachable    intro v    fin_cases v    · exact SimpleGraph.Reachable.rfl    · exact h01    · exact h02    · exact h03    · exact h04    · exact h05    · exact h06    · exact h07    · exact h08  · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]    decideprivate def blue_a : Set (Fin 9) := {0, 2, 3, 6}private def blue_b : Set (Fin 9) := {0, 8}private theorem blue_a_forcing : is_zero_forcing_set witness_graph blue_a := by  have h0 : ZeroForced witness_graph blue_a 0 := ZeroForced.init 0 (by simp [blue_a])  have h2 : ZeroForced witness_graph blue_a 2 := ZeroForced.init 2 (by simp [blue_a])  have h3 : ZeroForced witness_graph blue_a 3 := ZeroForced.init 3 (by simp [blue_a])  have h6 : ZeroForced witness_graph blue_a 6 := ZeroForced.init 6 (by simp [blue_a])  have h1 : ZeroForced witness_graph blue_a 1 := by    apply ZeroForced.step 2 1 h2 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h5 : ZeroForced witness_graph blue_a 5 := by    apply ZeroForced.step 0 5 h0 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h4 : ZeroForced witness_graph blue_a 4 := by    apply ZeroForced.step 3 4 h3 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h8 : ZeroForced witness_graph blue_a 8 := by    apply ZeroForced.step 5 8 h5 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h7 : ZeroForced witness_graph blue_a 7 := by    apply ZeroForced.step 6 7 h6 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  intro v  fin_cases v <;> assumptionprivate theorem blue_b_forcing : is_zero_forcing_set witness_graph blue_b := by  have h0 : ZeroForced witness_graph blue_b 0 := ZeroForced.init 0 (by simp [blue_b])  have h8 : ZeroForced witness_graph blue_b 8 := ZeroForced.init 8 (by simp [blue_b])  have h5 : ZeroForced witness_graph blue_b 5 := by    apply ZeroForced.step 8 5 h8 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h1 : ZeroForced witness_graph blue_b 1 := by    apply ZeroForced.step 0 1 h0 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h2 : ZeroForced witness_graph blue_b 2 := by    apply ZeroForced.step 1 2 h1 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h3 : ZeroForced witness_graph blue_b 3 := by    apply ZeroForced.step 2 3 h2 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h4 : ZeroForced witness_graph blue_b 4 := by    apply ZeroForced.step 3 4 h3 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h6 : ZeroForced witness_graph blue_b 6 := by    apply ZeroForced.step 5 6 h5 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  have h7 : ZeroForced witness_graph blue_b 7 := by    apply ZeroForced.step 6 7 h6 (by decide)    intro v hv hne    fin_cases v <;> simp_all [witness_graph, witness_edges]  intro v  fin_cases v <;> assumptionprivate theorem fort_blocking {V : Type*} (G : SimpleGraph V) (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 fort_blocks_complement {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (W F : Finset V) (hsub : F ⊆ W) (hne : F.Nonempty)    (hfort : ∀ u, u ∉ F → ∀ w, w ∈ F → G.Adj u w →      ∃ x, x ∈ F ∧ G.Adj u x ∧ x ≠ w) :    ¬ is_zero_forcing_set G ((Finset.univ \ W : Finset V) : Set V) := by  intro hS  obtain ⟨v, hv⟩ := hne  have hdisj : ∀ v, v ∈ (F : Set V) → v ∉ ((Finset.univ \ W : Finset V) : Set V) := by    intro x hxF hxS    exact (Finset.mem_sdiff.mp hxS).2 (hsub hxF)  have hf : ∀ u, u ∉ (F : Set V) → ∀ w, w ∈ (F : Set V) → G.Adj u w →      ∃ x, x ∈ (F : Set V) ∧ G.Adj u x ∧ x ≠ w := hfort  exact fort_blocking G ((Finset.univ \ W : Finset V) : Set V) (F : Set V) hdisj hf v (hS v) hvprivate theorem forced_mono {V : Type*} (G : SimpleGraph V) {S T : Set V} (h : S ⊆ T) :    ∀ v, ZeroForced G S v → ZeroForced G T v := by  intro v hv  induction hv with  | init v hvS => exact ZeroForced.init v (h hvS)  | step u w hu huw hothers ihu ihothers =>    exact ZeroForced.step u w ihu huw ihothersprivate def white_A : Finset (Fin 9) := {1, 4, 5, 7}private def white_B : Finset (Fin 9) := {1, 2, 3, 4, 5, 6, 7}private theorem blue_A_insert_forcing :    is_zero_forcing_set witness_graph      ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)) := by  have hset : ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)) = blue_a := by    ext v    fin_cases v <;> simp [white_A, blue_a]  rw [hset]  exact blue_a_forcingprivate theorem blue_B_forcing :    is_zero_forcing_set witness_graph ((Finset.univ \ white_B : Finset (Fin 9)) : Set (Fin 9)) := by  have hset : ((Finset.univ \ white_B : Finset (Fin 9)) : Set (Fin 9)) = blue_b := by    ext v    fin_cases v <;> simp [white_B, blue_b]  rw [hset]  exact blue_b_forcingprivate theorem blue_A_forcing :    is_zero_forcing_set witness_graph ((Finset.univ \ white_A : Finset (Fin 9)) : Set (Fin 9)) := by  intro v  apply forced_mono witness_graph (S := ((Finset.univ \ insert 8 white_A : Finset (Fin 9)) : Set (Fin 9)))  · intro x hx    exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, fun hxA => (Finset.mem_sdiff.mp hx).2 (Finset.mem_insert_of_mem hxA)⟩  · exact blue_A_insert_forcing vprivate theorem no_two_repairs (R : Finset (Fin 9)) (hR : R ⊆ white_B \ white_A)    (hcard : R.card ≤ 2) :    ¬ is_zero_forcing_set witness_graph      ((Finset.univ \ insert 8 (white_B \ R) : Finset (Fin 9)) : Set (Fin 9)) := by  have hBA : white_B \ white_A = ({2, 3, 6} : Finset (Fin 9)) := by decide  have hsub : R ⊆ ({2, 3, 6} : Finset (Fin 9)) := by simpa only [hBA] using hR  have h1 : (1 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh  have h4 : (4 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh  have h5 : (5 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh  have h7 : (7 : Fin 9) ∉ R := by intro h; have hh := hsub h; simp at hh  by_cases h2 : (2 : Fin 9) ∈ R <;> by_cases h3 : (3 : Fin 9) ∈ R <;> by_cases h6 : (6 : Fin 9) ∈ R  · have hthree : ({2, 3, 6} : Finset (Fin 9)) ⊆ R := by      intro x hx      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      rcases hx with rfl | rfl | rfl <;> assumption    have hc := Finset.card_le_card hthree    have hcard3 : ({2, 3, 6} : Finset (Fin 9)).card = 3 := by decide    rw [hcard3] at hc    omega  · apply fort_blocks_complement witness_graph _ ({6, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 3, 4, 5, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 3, 4, 5, 6, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 2, 4, 5, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 2, 4, 5, 6, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 2, 3, 4, 5, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decide  · apply fort_blocks_complement witness_graph _ ({1, 2, 3, 4, 5, 6, 7, 8} : Finset (Fin 9))    · intro x hx      fin_cases x <;> simp_all [white_B]    · decide    · decideprivate theorem witness_not_two_extendible :    ¬ (∀ A B : Finset (Fin 9), A ⊆ B →      is_zero_forcing_set witness_graph ((Finset.univ \ A : Finset (Fin 9)) : Set (Fin 9)) →      is_zero_forcing_set witness_graph ((Finset.univ \ B : Finset (Fin 9)) : Set (Fin 9)) →      ∀ x : Fin 9, x ∉ B →      is_zero_forcing_set witness_graph ((Finset.univ \ insert x A : Finset (Fin 9)) : Set (Fin 9)) →      ∃ R : Finset (Fin 9), R ⊆ B \ A ∧ R.card ≤ 2 ∧        is_zero_forcing_set witness_graph ((Finset.univ \ insert x (B \ R) : Finset (Fin 9)) : Set (Fin 9))) := by  intro h  have hab : white_A ⊆ white_B := by decide  have hx : (8 : Fin 9) ∉ white_B := by decide  obtain ⟨R, hR, hc, hforce⟩ := h white_A white_B hab blue_A_forcing blue_B_forcing 8 hx blue_A_insert_forcing  exact no_two_repairs R hR hc hforcetheorem tree_zero_forcing_complements_not_two_extendible : ∃ G : SimpleGraph (Fin 9), G.IsTree ∧ ¬ zero_forcing_complements_two_extendible G := by  exact ⟨witness_graph, witness_tree, witness_not_two_extendible⟩
See it in the graphDiscuss this resultChallenge it