tree_fort_free_nonpure_counterexample
A four-vertex tree has a maximal fort-free two-set and also a fort-free three-set.
Statement
theorem tree_fort_free_nonpure_counterexample : ∃ (G : SimpleGraph (Fin 4)) (A B : Finset (Fin 4)), G.IsTree ∧ A.card = 2 ∧ B.card = 3 ∧ is_zero_forcing_set G ((Finset.univ \ A : Finset (Fin 4)) : Set (Fin 4)) ∧ is_zero_forcing_set G ((Finset.univ \ B : Finset (Fin 4)) : Set (Fin 4)) ∧ ∀ x ∉ A, ¬ is_zero_forcing_set G ((Finset.univ \ insert x A : Finset (Fin 4)) : Set (Fin 4))- Source
- A four-vertex obstruction to a normalized-matching proof strategy for OP-1399.
- 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.…
- Arena.Reachable.transReachability is transitive.
The proof, explained
The theorem demonstrates that the property of being a maximal fort-free set is not pure (i.e., maximal fort-free sets can have different sizes), even on trees. A 4-vertex path graph G is constructed with vertices {0, 1, 2, 3} and edges (1, 0), (1, 2), and (0, 3). Then A = {2, 3} is shown to be a maximal fort-free set of size 2, while B = {0, 1, 2} is a fort-free set of size 3, with all properties verified by exhaustive finite check.
Adjacency in the graph is decidable
We simplify the definition of adjacency to membership in a finite edge list and conclude by instance synthesis.
intro u v dsimp [tree_fort_free_nonpure_counterexample_G, SimpleGraph.fromRel] infer_instance
The graph G is a tree
A graph is a tree if and only if it is connected and has |V| - 1 edges. Connectivity is shown by reaching all vertices from 0, and the edge and vertex counts are verified by computation.
uses
SimpleGraph.isTree_iff_connected_and_cardrw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩ · rw [SimpleGraph.connected_iff_exists_forall_reachable] use 0 intro w fin_cases w · exact SimpleGraph.Reachable.refl 0 · have h : tree_fort_free_nonpure_counterexample_G.Adj 0 1 := by decide exact h.reachable · have h01 : tree_fort_free_nonpure_counterexample_G.Adj 0 1 := by decide have h12 : tree_fort_free_nonpure_counterexample_G.Adj 1 2 := by decide exact h01.reachable.trans h12.reachable · have h03 : tree_fort_free_nonpure_counterexample_G.Adj 0 3 := by decide exact h03.reachable · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decide
The four-vertex path exhibits a maximal fort-free 2-set and a fort-free 3-set
We provide the 4-vertex path graph with sets A = {2, 3} and B = {0, 1, 2}. Their cardinalities and fort-free property (i.e. their complements being zero forcing sets) are checked by finite exhaustive search, as is the fact that adding any vertex outside A creates a fort.
refine ⟨tree_fort_free_nonpure_counterexample_G, {2, 3}, {0, 1, 2}, tree_fort_free_nonpure_counterexample_isTree, by decide, by decide, ?_, ?_, ?_⟩ · rw [zfs_compl_iff_no_stuck] decide · rw [zfs_compl_iff_no_stuck] decide · intro x hx rw [zfs_compl_iff_no_stuck] fin_cases x · decide · decide · exfalso; apply hx; decide · exfalso; apply hx; 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.
def tree_fort_free_nonpure_counterexample_edges : List (Fin 4 × Fin 4) := [(1, 0), (1, 2), (0, 3)]def tree_fort_free_nonpure_counterexample_G : SimpleGraph (Fin 4) := SimpleGraph.fromRel (fun u v => (u, v) ∈ tree_fort_free_nonpure_counterexample_edges)instance : DecidableRel tree_fort_free_nonpure_counterexample_G.Adj := by intro u v dsimp [tree_fort_free_nonpure_counterexample_G, SimpleGraph.fromRel] infer_instancelemma tree_fort_free_nonpure_counterexample_isTree : tree_fort_free_nonpure_counterexample_G.IsTree := by rw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩ · rw [SimpleGraph.connected_iff_exists_forall_reachable] use 0 intro w fin_cases w · exact SimpleGraph.Reachable.refl 0 · have h : tree_fort_free_nonpure_counterexample_G.Adj 0 1 := by decide exact h.reachable · have h01 : tree_fort_free_nonpure_counterexample_G.Adj 0 1 := by decide have h12 : tree_fort_free_nonpure_counterexample_G.Adj 1 2 := by decide exact h01.reachable.trans h12.reachable · have h03 : tree_fort_free_nonpure_counterexample_G.Adj 0 3 := by decide exact h03.reachable · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decidetheorem tree_fort_free_nonpure_counterexample : ∃ (G : SimpleGraph (Fin 4)) (A B : Finset (Fin 4)), G.IsTree ∧ A.card = 2 ∧ B.card = 3 ∧ is_zero_forcing_set G ((Finset.univ \ A : Finset (Fin 4)) : Set (Fin 4)) ∧ is_zero_forcing_set G ((Finset.univ \ B : Finset (Fin 4)) : Set (Fin 4)) ∧ ∀ x ∉ A, ¬ is_zero_forcing_set G ((Finset.univ \ insert x A : Finset (Fin 4)) : Set (Fin 4)) := by refine ⟨tree_fort_free_nonpure_counterexample_G, {2, 3}, {0, 1, 2}, tree_fort_free_nonpure_counterexample_isTree, by decide, by decide, ?_, ?_, ?_⟩ · rw [zfs_compl_iff_no_stuck] decide · rw [zfs_compl_iff_no_stuck] decide · intro x hx rw [zfs_compl_iff_no_stuck] fin_cases x · decide · decide · exfalso; apply hx; decide · exfalso; apply hx; decide