tree_zero_forcing_complements_not_two_extendible
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.
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.
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
`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`.
uses
SimpleGraph.isTree_iff_connected_and_card.mpr,SimpleGraph.Reachable.rfl,Nat.card_eq_fintype_cardprivate 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
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.
uses
ZeroForced.init,ZeroForced.stepprivate 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
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.
uses
ZeroForced.init,ZeroForced.stepprivate 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
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.
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
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.
uses
Finset.mem_sdiff.mp,fort_blockingprivate 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
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.
uses
ZeroForced.init,ZeroForced.stepprivate 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}
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`).
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.mprprivate 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
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.
uses
Finset.card_le_card,fort_blocks_complementprivate 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
`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`.
uses
blue_A_forcing,blue_B_forcing,blue_A_insert_forcing,no_two_repairsprivate 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
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.
uses
witness_tree,witness_not_two_extendibletheorem 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.
- In `witness_tree`, checking that the graph has 8 edges on 9 vertices, as well as the connectivity across all pairs from vertex 0, is discharged by finite decision procedures (`decide`).
- In `no_two_repairs`, the fact that each of the seven candidate sets is indeed a fort (that every outside neighbor has at least two neighbors in the set) is verified by exhaustive computation over `Fin 9` via `decide`.
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.
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⟩