AFTD Auto-Formalizing Theoretical Domains

tree_fort_free_nonpure_counterexample

theoremverified

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.

  1. Adjacency in the graph is decidable

    We simplify the definition of adjacency to membership in a finite edge list and conclude by instance synthesis.

    lines 8–10

      intro u v
      dsimp [tree_fort_free_nonpure_counterexample_G, SimpleGraph.fromRel]
      infer_instance
  2. 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.

    lines 13–28

    uses SimpleGraph.isTree_iff_connected_and_card

      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]
        decide
  3. 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.

    lines 31–43

      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

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