AFTD Auto-Formalizing Theoretical Domains

tree_exposure_plain_partial_sync_counterexample

theoremverified

For a rooted three-vertex path the unexposed counts at ranks zero and one are one and three, while the exposed counts at ranks zero, one and two are zero, zero and one; thus the two sequences fail ordinary partial synchronization.

Statement

theorem tree_exposure_plain_partial_sync_counterexample : ∃ (T : SimpleGraph (Fin 3)) (r : Fin 3), T.IsTree ∧ zero_forcing_root_exposure_count T r 0 false = 1 ∧ zero_forcing_root_exposure_count T r 1 false = 3 ∧ zero_forcing_root_exposure_count T r 0 true = 0 ∧ zero_forcing_root_exposure_count T r 1 true = 0 ∧ zero_forcing_root_exposure_count T r 2 true = 1
Source
An elementary obstruction to a proposed ordinary log-concavity route for OP-1399.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • zero_forcing_root_exposure_countThe number of k-element white vertex sets whose complement is zero forcing and whose root-exposed-fort status equals the given Boolean.
  • ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
  • is_zero_forcing_set_monoIf S is a zero forcing set of a simple graph G and S is a subset of S', then S' is also a zero forcing set of G.
  • zero_forcing_root_exposed_fortA white set W contains a root-exposed fort if it contains a set F not containing r such that r has a neighbor in F and every vertex other…
  • inst_decidableRel_pathGraphAdjacency in the path graph pathGraph n is decidable.
  • 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.
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.

The proof, explained

The theorem is established by exhibiting an explicit counterexample: the 3-vertex path graph P₃ with vertices {0, 1, 2} rooted at vertex 0. First, zero forcing is verified from either endpoint {0} or {2}, showing that the complement of any set omitting an endpoint is zero forcing. Next, root-exposed forts are classified, showing that any root-exposed fort must contain {1, 2}, which makes {1, 2} the unique exposed subset of size at most 2. By exhaustive counting over all subsets of sizes 0, 1, and 2, the unexposed counts are found to be 1 (rank 0) and 3 (rank 1), while the exposed counts are 0 (ranks 0 and 1) and 1 (rank 2), demonstrating the failure of ordinary partial synchronization.

  1. Neither vertex 0 nor vertex 2 is adjacent to itself, and vertices 0 and 2 are not adjacent to each other in pathGraph 3.

    Two vertices in pathGraph 3 are adjacent if and only if their numerical values differ by 1. For each pair (0,0), (0,2), (2,0), and (2,2), the adjacency definition evaluates to false.

    lines 3–6

    uses pathGraph_adj

    lemma tree_exposure_plain_partial_sync_counterexample_not_adj_0_0 : ¬ (pathGraph 3).Adj 0 0 := by rw [pathGraph_adj]; decide
    lemma tree_exposure_plain_partial_sync_counterexample_not_adj_0_2 : ¬ (pathGraph 3).Adj 0 2 := by rw [pathGraph_adj]; decide
    lemma tree_exposure_plain_partial_sync_counterexample_not_adj_2_0 : ¬ (pathGraph 3).Adj 2 0 := by rw [pathGraph_adj]; decide
    lemma tree_exposure_plain_partial_sync_counterexample_not_adj_2_2 : ¬ (pathGraph 3).Adj 2 2 := by rw [pathGraph_adj]; decide
  2. The singleton set {0} is a zero forcing set of pathGraph 3.

    Vertex 0 is initially in {0} and thus forced. Since 0 is adjacent to 1 and not to 0 or 2, vertex 0 forces vertex 1. With 0 already forced, vertex 1 forces vertex 2. Case analysis over all three vertices of Fin 3 confirms that every vertex is forced.

    lines 8–31

    uses ZeroForced.init, pathGraph_adj, ZeroForced.step, False.elim, tree_exposure_plain_partial_sync_counterexample_not_adj_0_0, tree_exposure_plain_partial_sync_counterexample_not_adj_0_2

    lemma tree_exposure_plain_partial_sync_counterexample_zf_zero : is_zero_forcing_set (pathGraph 3) ({0} : Set (Fin 3)) := by
      intro v
      have h0 : ZeroForced (pathGraph 3) {0} 0 := ZeroForced.init 0 (by simp)
      have hadj01 : (pathGraph 3).Adj 0 1 := by rw [pathGraph_adj]; decide
      have h1 : ZeroForced (pathGraph 3) {0} 1 := by
        apply ZeroForced.step 0 1 h0 hadj01
        intro x hx hne
        fin_cases x
        · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_0_0 hx)
        · contradiction
        · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_0_2 hx)
      have hadj12 : (pathGraph 3).Adj 1 2 := by rw [pathGraph_adj]; decide
      have h2 : ZeroForced (pathGraph 3) {0} 2 := by
        apply ZeroForced.step 1 2 h1 hadj12
        intro x hx hne
        fin_cases x
        · exact h0
        · exfalso; revert hx; rw [pathGraph_adj]; decide
        · contradiction
      fin_cases v
      · exact h0
      · exact h1
      · exact h2
    
  3. The singleton set {2} is a zero forcing set of pathGraph 3.

    Symmetrically, vertex 2 is initially in {2} and forced. Because its only neighbor is 1, vertex 2 forces vertex 1. Then vertex 1, having its other neighbor 2 already forced, forces vertex 0. Exhausting all vertices shows every vertex is forced.

    lines 32–55

    uses ZeroForced.init, pathGraph_adj, ZeroForced.step, False.elim, tree_exposure_plain_partial_sync_counterexample_not_adj_2_0, tree_exposure_plain_partial_sync_counterexample_not_adj_2_2

    lemma tree_exposure_plain_partial_sync_counterexample_zf_two : is_zero_forcing_set (pathGraph 3) ({2} : Set (Fin 3)) := by
      intro v
      have h2 : ZeroForced (pathGraph 3) {2} 2 := ZeroForced.init 2 (by simp)
      have hadj21 : (pathGraph 3).Adj 2 1 := by rw [pathGraph_adj]; decide
      have h1 : ZeroForced (pathGraph 3) {2} 1 := by
        apply ZeroForced.step 2 1 h2 hadj21
        intro x hx hne
        fin_cases x
        · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_2_0 hx)
        · contradiction
        · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_2_2 hx)
      have hadj10 : (pathGraph 3).Adj 1 0 := by rw [pathGraph_adj]; decide
      have h0 : ZeroForced (pathGraph 3) {2} 0 := by
        apply ZeroForced.step 1 0 h1 hadj10
        intro x hx hne
        fin_cases x
        · contradiction
        · exfalso; revert hx; rw [pathGraph_adj]; decide
        · exact h2
      fin_cases v
      · exact h0
      · exact h1
      · exact h2
    
  4. For any subset W ⊆ Fin 3, if 0 ∉ W or 2 ∉ W, then its complement V \\ W is a zero forcing set.

    If 0 ∉ W, then {0} ⊆ V \\ W, so V \\ W is zero forcing by monotonicity from the fact that {0} is zero forcing. Similarly, if 2 ∉ W, then {2} ⊆ V \\ W, which is zero forcing by monotonicity from {2}.

    lines 56–73

    uses is_zero_forcing_set_mono, Set.mem_singleton_iff, tree_exposure_plain_partial_sync_counterexample_zf_zero, tree_exposure_plain_partial_sync_counterexample_zf_two

    lemma tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem (W : Finset (Fin 3)) (h : 0 ∉ W ∨ 2 ∉ W) :
        is_zero_forcing_set (pathGraph 3) (((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3))) := by
      cases h with
      | inl h0 =>
        apply is_zero_forcing_set_mono (pathGraph 3) (S := {0})
        · intro x hx
          simp only [Set.mem_singleton_iff] at hx
          subst hx
          simp [h0]
        · exact tree_exposure_plain_partial_sync_counterexample_zf_zero
      | inr h2 =>
        apply is_zero_forcing_set_mono (pathGraph 3) (S := {2})
        · intro x hx
          simp only [Set.mem_singleton_iff] at hx
          subst hx
          simp [h2]
        · exact tree_exposure_plain_partial_sync_counterexample_zf_two
    
  5. The subset {1, 2} is a root-exposed fort for root 0 in pathGraph 3.

    Choosing the fort F = {1, 2} ⊆ {1, 2}, we have 0 ∉ F, and root 0 has neighbor 1 ∈ F. Any vertex u ≠ 0 with u ∉ F would belong to {0, 1, 2} \\ ({1, 2} ∪ {0}), which is empty; thus the fort condition for outside vertices holds vacuously.

    lines 74–81

    uses subset_rfl, pathGraph_adj

    lemma tree_exposure_plain_partial_sync_counterexample_exposed_12 : zero_forcing_root_exposed_fort (pathGraph 3) 0 {1, 2} := by
      refine ⟨{1, 2}, subset_rfl, by decide, ⟨1, by decide, by rw [pathGraph_adj]; decide⟩, ?_⟩
      intro u hu_ne hu_not w hw hadj
      fin_cases u
      · contradiction
      · exfalso; apply hu_not; decide
      · exfalso; apply hu_not; decide
    
  6. If W ⊆ Fin 3 does not contain {1, 2}, then W does not contain any root-exposed fort for root 0.

    Suppose a root-exposed fort F ⊆ W exists. Since {1, 2} ⊈ W, either 1 ∉ W or 2 ∉ W. If 1 ∉ W, then 1 ∉ F; but F must contain a neighbor of 0, and the only neighbor of 0 is 1, a contradiction. If 2 ∉ W, then 2 ∉ F, and the neighbor of 0 in F is again 1; then vertex 2 is outside F, adjacent to 1 ∈ F, so the fort property requires 2 to have another neighbor in F, which is impossible because 2 has no other neighbors in pathGraph 3.

    lines 82–129

    uses pathGraph_adj

    lemma tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset (W : Finset (Fin 3)) (h : ¬ ({1, 2} : Finset (Fin 3)) ⊆ W) :
        ¬ zero_forcing_root_exposed_fort (pathGraph 3) 0 W := by
      intro ⟨F, hFW, hrF, ⟨w, hwF, hadj0w⟩, hfort⟩
      have h12 : 1 ∉ W ∨ 2 ∉ W := by
        by_contra hc
        push Not at hc
        apply h
        intro x hx
        fin_cases x
        · exfalso; revert hx; decide
        · exact hc.1
        · exact hc.2
      cases h12 with
      | inl h1W =>
        have h1F : 1 ∉ F := fun h => h1W (hFW h)
        have : w = 1 := by
          rw [pathGraph_adj] at hadj0w
          fin_cases w
          · revert hadj0w; decide
          · rfl
          · revert hadj0w; decide
        subst this
        exact h1F hwF
      | inr h2W =>
        have h2F : 2 ∉ F := fun h => h2W (hFW h)
        have hw1 : w = 1 := by
          rw [pathGraph_adj] at hadj0w
          fin_cases w
          · revert hadj0w; decide
          · rfl
          · revert hadj0w; decide
        have h2ne0 : (2 : Fin 3) ≠ 0 := by decide
        have h2adj1 : (pathGraph 3).Adj 2 1 := by rw [pathGraph_adj]; decide
        obtain ⟨x, hxF, hadj2x, hxnew⟩ := hfort 2 h2ne0 h2F w hwF (hw1 ▸ h2adj1)
        have : x = 1 := by
          have : x ≠ 0 := by
            intro hx0
            subst hx0
            revert hadj2x
            rw [pathGraph_adj]; decide
          have : x ≠ 2 := fun hx2 => h2F (hx2 ▸ hxF)
          fin_cases x
          · contradiction
          · rfl
          · contradiction
        apply hxnew
        rw [hw1, this]
    
  7. Every subset of Fin 3 of cardinality 1 is {0}, {1}, or {2}.

    A finite set of cardinality 1 is a singleton {x}, and exhausting the three possible values of x in Fin 3 yields {0}, {1}, or {2}.

    lines 130–134

    uses Finset.card_eq_one.mp

    lemma tree_exposure_plain_partial_sync_counterexample_finset_card_one (W : Finset (Fin 3)) (h : W.card = 1) :
        W = {0} ∨ W = {1} ∨ W = {2} := by
      obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp h
      fin_cases x <;> simp
    
  8. Every subset of Fin 3 of cardinality 2 is {0, 1}, {0, 2}, or {1, 2}.

    If |W| = 2, its complement in the 3-element universe has cardinality 3 - 2 = 1, so the complement is {x} for some x ∈ Fin 3. Thus W is the complement of {x}, which by case analysis on x gives {1, 2}, {0, 2}, or {0, 1}.

    lines 135–148

    uses Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Fintype.card_fin, Finset.card_eq_one.mp, Finset.sdiff_sdiff_eq_self

    lemma tree_exposure_plain_partial_sync_counterexample_finset_card_two (W : Finset (Fin 3)) (h : W.card = 2) :
        W = {0, 1} ∨ W = {0, 2} ∨ W = {1, 2} := by
      have h1 : (Finset.univ \ W).card = 1 := by
        rw [Finset.card_sdiff_of_subset (Finset.subset_univ W), Finset.card_univ, Fintype.card_fin, h]
      obtain ⟨x, hx⟩ := Finset.card_eq_one.mp h1
      have hw : W = Finset.univ \ {x} := by
        have := Finset.sdiff_sdiff_eq_self (Finset.subset_univ W)
        rw [hx] at this
        exact this.symm
      fin_cases x
      · right; right; rw [hw]; decide
      · right; left; rw [hw]; decide
      · left; rw [hw]; decide
    
  9. pathGraph 3 is a tree.

    A finite graph is a tree if and only if it is connected and has |V| - 1 edges. The path graph on 3 vertices is connected and has 2 edges, as verified by direct computation.

    lines 149–154

    uses SimpleGraph.isTree_iff_connected_and_card, SimpleGraph.pathGraph_connected, Nat.card_fin, Nat.card_eq_fintype_card, SimpleGraph.edgeFinset_card

    lemma tree_exposure_plain_partial_sync_counterexample_isTree : (pathGraph 3).IsTree := by
      rw [SimpleGraph.isTree_iff_connected_and_card]
      refine ⟨SimpleGraph.pathGraph_connected 2, ?_⟩
      rw [Nat.card_fin, Nat.card_eq_fintype_card, <- SimpleGraph.edgeFinset_card]
      decide
    
  10. The unexposed count at rank 0 is 1.

    The only subset of size 0 is ∅. Its complement is all of V, which is zero forcing because 0 ∉ ∅; and ∅ does not contain {1, 2}, so it is not root-exposed. Thus the set of qualifying subsets is {∅}, which has cardinality 1.

    lines 155–170

    uses Set.mem_singleton_iff, Finset.card_eq_zero.mp, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem, Or.inl, Bool.false_eq_true, false_iff, tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset, Set.ncard_singleton

    lemma tree_exposure_plain_partial_sync_counterexample_c_0_false : zero_forcing_root_exposure_count (pathGraph 3) 0 0 false = 1 := by
      unfold zero_forcing_root_exposure_count
      have : {W : Finset (Fin 3) | W.card = 0 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((false = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = {∅} := by
        ext W
        simp only [Set.mem_singleton_iff]
        constructor
        · rintro ⟨hcard, -⟩
          exact Finset.card_eq_zero.mp hcard
        · rintro rfl
          refine ⟨rfl, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem ∅ (Or.inl (by decide)), ?_⟩
          simp only [Bool.false_eq_true, false_iff]
          apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset
          decide
      rw [this]
      exact Set.ncard_singleton ∅
    
  11. The exposed count at rank 0 is 0.

    Any subset of size 0 must be ∅, but ∅ does not contain {1, 2} and therefore cannot be root-exposed. Hence the set of such subsets is empty, with cardinality 0.

    lines 171–185

    uses Finset.card_eq_zero.mp, tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset, False.elim, Set.ncard_empty

    lemma tree_exposure_plain_partial_sync_counterexample_c_0_true : zero_forcing_root_exposure_count (pathGraph 3) 0 0 true = 0 := by
      unfold zero_forcing_root_exposure_count
      have : {W : Finset (Fin 3) | W.card = 0 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ∅ := by
        ext W
        constructor
        · rintro ⟨hcard, _, he⟩
          have : W = ∅ := Finset.card_eq_zero.mp hcard
          subst this
          have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 ∅ := he.mp rfl
          have hnot := tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset ∅ (by decide)
          exact hnot hexp
        · intro h
          exact False.elim h
      rw [this, Set.ncard_empty]
    
  12. The exposed count at rank 1 is 0.

    Any root-exposed fort must contain {1, 2}, which has 2 elements, so its cardinality must be at least 2. Therefore, no subset of cardinality 1 can be root-exposed, making the set of qualifying subsets empty.

    lines 186–203

    uses tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset, Finset.card_le_card, False.elim, Set.ncard_empty

    lemma tree_exposure_plain_partial_sync_counterexample_c_1_true : zero_forcing_root_exposure_count (pathGraph 3) 0 1 true = 0 := by
      unfold zero_forcing_root_exposure_count
      have : {W : Finset (Fin 3) | W.card = 1 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ∅ := by
        ext W
        constructor
        · rintro ⟨hcard, _, he⟩
          have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 W := he.mp rfl
          have hnot : ¬ zero_forcing_root_exposed_fort (pathGraph 3) 0 W := by
            apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset
            intro hsub
            have hc : ({1, 2} : Finset (Fin 3)).card = 2 := by decide
            have : ({1, 2} : Finset (Fin 3)).card ≤ W.card := Finset.card_le_card hsub
            omega
          exact hnot hexp
        · intro h
          exact False.elim h
      rw [this, Set.ncard_empty]
    
  13. The exposed count at rank 2 is 1.

    Every 2-element subset is {0, 1}, {0, 2}, or {1, 2}. The first two do not contain {1, 2} and cannot be root-exposed. The subset {1, 2} is root-exposed and its complement {0} is zero forcing because 0 ∉ {1, 2}. Hence {1, 2} is the unique such subset, giving count 1.

    lines 204–223

    uses tree_exposure_plain_partial_sync_counterexample_finset_card_two, tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset, Set.mem_singleton_iff.mpr, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem, Or.inl, tree_exposure_plain_partial_sync_counterexample_exposed_12, Set.ncard_singleton

    lemma tree_exposure_plain_partial_sync_counterexample_c_2_true : zero_forcing_root_exposure_count (pathGraph 3) 0 2 true = 1 := by
      unfold zero_forcing_root_exposure_count
      have : {W : Finset (Fin 3) | W.card = 2 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = {{1, 2}} := by
        ext W
        constructor
        · rintro ⟨hcard, _, he⟩
          have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 W := he.mp rfl
          obtain (h | h | h) := tree_exposure_plain_partial_sync_counterexample_finset_card_two W hcard
          · exfalso
            subst h
            exact tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset {0, 1} (by decide) hexp
          · exfalso
            subst h
            exact tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset {0, 2} (by decide) hexp
          · exact Set.mem_singleton_iff.mpr h
        · rintro rfl
          refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {1, 2} (Or.inl (by decide)), ?_⟩
          simp [tree_exposure_plain_partial_sync_counterexample_exposed_12]
      rw [this, Set.ncard_singleton]
    
  14. The unexposed count at rank 1 is 3.

    The 1-element subsets are {0}, {1}, and {2}. None contains {1, 2}, so none is root-exposed. For each, at least one endpoint 0 or 2 is omitted, so the complement is zero forcing. Thus all three singletons qualify, giving a count of 3.

    lines 224–244

    uses Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, tree_exposure_plain_partial_sync_counterexample_finset_card_one, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem, Or.inr, Bool.false_eq_true, false_iff, tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset, Or.inl, Set.ncard_coe_finset

    lemma tree_exposure_plain_partial_sync_counterexample_c_1_false : zero_forcing_root_exposure_count (pathGraph 3) 0 1 false = 3 := by
      unfold zero_forcing_root_exposure_count
      have : {W : Finset (Fin 3) | W.card = 1 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((false = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ({{0}, {1}, {2}} : Finset (Finset (Fin 3))) := by
        ext W
        simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · rintro ⟨hcard, _, _⟩
          exact tree_exposure_plain_partial_sync_counterexample_finset_card_one W hcard
        · rintro (rfl | rfl | rfl)
          · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {0} (Or.inr (by decide)), ?_⟩
            simp only [Bool.false_eq_true, false_iff]
            apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide
          · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {1} (Or.inl (by decide)), ?_⟩
            simp only [Bool.false_eq_true, false_iff]
            apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide
          · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {2} (Or.inl (by decide)), ?_⟩
            simp only [Bool.false_eq_true, false_iff]
            apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide
      rw [this, Set.ncard_coe_finset]
      decide
    
  15. There exists a rooted tree on 3 vertices whose unexposed counts at ranks 0 and 1 are 1 and 3, and whose exposed counts at ranks 0, 1, and 2 are 0, 0, and 1.

    The 3-vertex path graph pathGraph 3 with root 0 provides the witness: it is a tree and its five exposure counts match the previously established values.

    lines 245–251

    uses tree_exposure_plain_partial_sync_counterexample_isTree, tree_exposure_plain_partial_sync_counterexample_c_0_false, tree_exposure_plain_partial_sync_counterexample_c_1_false, tree_exposure_plain_partial_sync_counterexample_c_0_true, tree_exposure_plain_partial_sync_counterexample_c_1_true, tree_exposure_plain_partial_sync_counterexample_c_2_true

    theorem tree_exposure_plain_partial_sync_counterexample : ∃ (T : SimpleGraph (Fin 3)) (r : Fin 3), T.IsTree ∧ zero_forcing_root_exposure_count T r 0 false = 1 ∧ zero_forcing_root_exposure_count T r 1 false = 3 ∧ zero_forcing_root_exposure_count T r 0 true = 0 ∧ zero_forcing_root_exposure_count T r 1 true = 0 ∧ zero_forcing_root_exposure_count T r 2 true = 1 := by
      refine ⟨pathGraph 3, 0, tree_exposure_plain_partial_sync_counterexample_isTree,
        tree_exposure_plain_partial_sync_counterexample_c_0_false,
        tree_exposure_plain_partial_sync_counterexample_c_1_false,
        tree_exposure_plain_partial_sync_counterexample_c_0_true,
        tree_exposure_plain_partial_sync_counterexample_c_1_true,
        tree_exposure_plain_partial_sync_counterexample_c_2_true⟩
pathGraph_adj
Two vertices u, v in pathGraph n are adjacent if and only if u + 1 = v or v + 1 = u.
ZeroForced.init
Any vertex initially in S is zero-forced by S.
ZeroForced.step
If u is zero-forced, w is adjacent to u, and every other neighbor of u is already zero-forced, then w is zero-forced.
False.elim
From False, any proposition follows.
tree_exposure_plain_partial_sync_counterexample_not_adj_0_0
In pathGraph 3, vertex 0 is not adjacent to itself.
tree_exposure_plain_partial_sync_counterexample_not_adj_0_2
In pathGraph 3, vertex 0 is not adjacent to vertex 2.
tree_exposure_plain_partial_sync_counterexample_not_adj_2_0
In pathGraph 3, vertex 2 is not adjacent to vertex 0.
tree_exposure_plain_partial_sync_counterexample_not_adj_2_2
In pathGraph 3, vertex 2 is not adjacent to itself.
is_zero_forcing_set_mono
If S ⊆ S' and S is a zero forcing set of G, then S' is also a zero forcing set of G.
Set.mem_singleton_iff
An element a belongs to {b} if and only if a = b.
Set.mem_singleton_iff.mpr
If a = b, then a belongs to {b}.
tree_exposure_plain_partial_sync_counterexample_zf_zero
The singleton {0} is a zero forcing set of pathGraph 3.
tree_exposure_plain_partial_sync_counterexample_zf_two
The singleton {2} is a zero forcing set of pathGraph 3.
subset_rfl
Every set is a subset of itself.
Finset.card_eq_one.mp
If a finite set has cardinality 1, it is a singleton {a}.
Finset.card_eq_zero.mp
If a finite set has cardinality 0, it is the empty set ∅.
Finset.card_sdiff_of_subset
If s ⊆ t for finite sets, then |t \\ s| = |t| - |s|.
Finset.subset_univ
Every finite set is a subset of the universal finset.
Finset.card_univ
The cardinality of the universal finset of a type is the cardinality of the type.
Fintype.card_fin
The type Fin n has cardinality n.
Finset.sdiff_sdiff_eq_self
For finite sets t ⊆ s, the complement of the complement s \\ (s \\ t) equals t.
SimpleGraph.isTree_iff_connected_and_card
A finite graph is a tree if and only if it is connected and its edge count plus 1 equals its vertex count.
SimpleGraph.pathGraph_connected
The path graph on n + 1 vertices is connected.
Nat.card_fin
The cardinality of the set Fin n is n.
Nat.card_eq_fintype_card
For a finite type, its cardinality as a type equals its Fintype cardinality.
SimpleGraph.edgeFinset_card
The cardinality of the edge finset equals the cardinality of the edge set.
tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem
For any subset W of vertices in pathGraph 3, if 0 ∉ W or 2 ∉ W, then the complement V \\ W is a zero forcing set.
Or.inl
Constructs a proof of A ∨ B from a proof of A.
Or.inr
Constructs a proof of A ∨ B from a proof of B.
Bool.false_eq_true
The equality false = true is false.
false_iff
False ↔ p is equivalent to ¬p.
tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset
If a vertex subset W in pathGraph 3 does not contain {1, 2}, it cannot contain a root-exposed fort for root 0.
Set.ncard_singleton
The cardinality of a singleton set is 1.
Set.ncard_empty
The cardinality of the empty set is 0.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
tree_exposure_plain_partial_sync_counterexample_finset_card_two
Any 2-element subset of Fin 3 is {0, 1}, {0, 2}, or {1, 2}.
tree_exposure_plain_partial_sync_counterexample_finset_card_one
Any 1-element subset of Fin 3 is {0}, {1}, or {2}.
tree_exposure_plain_partial_sync_counterexample_exposed_12
The subset {1, 2} is a root-exposed fort for root 0 in pathGraph 3.
Finset.mem_coe
Membership in a coerced finset is equivalent to membership in the finset.
Finset.mem_insert
Membership in insert b s is equivalent to being equal to b or being in s.
Finset.mem_singleton
Membership in the finset singleton {a} is equivalent to equality with a.
Set.ncard_coe_finset
The set cardinality of a coerced finset equals its finset cardinality.
tree_exposure_plain_partial_sync_counterexample_isTree
pathGraph 3 is a tree.
tree_exposure_plain_partial_sync_counterexample_c_0_false
In pathGraph 3 rooted at 0, the unexposed count at rank 0 is 1.
tree_exposure_plain_partial_sync_counterexample_c_1_false
In pathGraph 3 rooted at 0, the unexposed count at rank 1 is 3.
tree_exposure_plain_partial_sync_counterexample_c_0_true
In pathGraph 3 rooted at 0, the exposed count at rank 0 is 0.
tree_exposure_plain_partial_sync_counterexample_c_1_true
In pathGraph 3 rooted at 0, the exposed count at rank 1 is 0.
tree_exposure_plain_partial_sync_counterexample_c_2_true
In pathGraph 3 rooted at 0, the exposed count at rank 2 is 1.

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

open SimpleGraphlemma tree_exposure_plain_partial_sync_counterexample_not_adj_0_0 : ¬ (pathGraph 3).Adj 0 0 := by rw [pathGraph_adj]; decidelemma tree_exposure_plain_partial_sync_counterexample_not_adj_0_2 : ¬ (pathGraph 3).Adj 0 2 := by rw [pathGraph_adj]; decidelemma tree_exposure_plain_partial_sync_counterexample_not_adj_2_0 : ¬ (pathGraph 3).Adj 2 0 := by rw [pathGraph_adj]; decidelemma tree_exposure_plain_partial_sync_counterexample_not_adj_2_2 : ¬ (pathGraph 3).Adj 2 2 := by rw [pathGraph_adj]; decidelemma tree_exposure_plain_partial_sync_counterexample_zf_zero : is_zero_forcing_set (pathGraph 3) ({0} : Set (Fin 3)) := by  intro v  have h0 : ZeroForced (pathGraph 3) {0} 0 := ZeroForced.init 0 (by simp)  have hadj01 : (pathGraph 3).Adj 0 1 := by rw [pathGraph_adj]; decide  have h1 : ZeroForced (pathGraph 3) {0} 1 := by    apply ZeroForced.step 0 1 h0 hadj01    intro x hx hne    fin_cases x    · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_0_0 hx)    · contradiction    · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_0_2 hx)  have hadj12 : (pathGraph 3).Adj 1 2 := by rw [pathGraph_adj]; decide  have h2 : ZeroForced (pathGraph 3) {0} 2 := by    apply ZeroForced.step 1 2 h1 hadj12    intro x hx hne    fin_cases x    · exact h0    · exfalso; revert hx; rw [pathGraph_adj]; decide    · contradiction  fin_cases v  · exact h0  · exact h1  · exact h2lemma tree_exposure_plain_partial_sync_counterexample_zf_two : is_zero_forcing_set (pathGraph 3) ({2} : Set (Fin 3)) := by  intro v  have h2 : ZeroForced (pathGraph 3) {2} 2 := ZeroForced.init 2 (by simp)  have hadj21 : (pathGraph 3).Adj 2 1 := by rw [pathGraph_adj]; decide  have h1 : ZeroForced (pathGraph 3) {2} 1 := by    apply ZeroForced.step 2 1 h2 hadj21    intro x hx hne    fin_cases x    · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_2_0 hx)    · contradiction    · exact False.elim (tree_exposure_plain_partial_sync_counterexample_not_adj_2_2 hx)  have hadj10 : (pathGraph 3).Adj 1 0 := by rw [pathGraph_adj]; decide  have h0 : ZeroForced (pathGraph 3) {2} 0 := by    apply ZeroForced.step 1 0 h1 hadj10    intro x hx hne    fin_cases x    · contradiction    · exfalso; revert hx; rw [pathGraph_adj]; decide    · exact h2  fin_cases v  · exact h0  · exact h1  · exact h2lemma tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem (W : Finset (Fin 3)) (h : 0 ∉ W ∨ 2 ∉ W) :    is_zero_forcing_set (pathGraph 3) (((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3))) := by  cases h with  | inl h0 =>    apply is_zero_forcing_set_mono (pathGraph 3) (S := {0})    · intro x hx      simp only [Set.mem_singleton_iff] at hx      subst hx      simp [h0]    · exact tree_exposure_plain_partial_sync_counterexample_zf_zero  | inr h2 =>    apply is_zero_forcing_set_mono (pathGraph 3) (S := {2})    · intro x hx      simp only [Set.mem_singleton_iff] at hx      subst hx      simp [h2]    · exact tree_exposure_plain_partial_sync_counterexample_zf_twolemma tree_exposure_plain_partial_sync_counterexample_exposed_12 : zero_forcing_root_exposed_fort (pathGraph 3) 0 {1, 2} := by  refine ⟨{1, 2}, subset_rfl, by decide, ⟨1, by decide, by rw [pathGraph_adj]; decide⟩, ?_⟩  intro u hu_ne hu_not w hw hadj  fin_cases u  · contradiction  · exfalso; apply hu_not; decide  · exfalso; apply hu_not; decidelemma tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset (W : Finset (Fin 3)) (h : ¬ ({1, 2} : Finset (Fin 3)) ⊆ W) :    ¬ zero_forcing_root_exposed_fort (pathGraph 3) 0 W := by  intro ⟨F, hFW, hrF, ⟨w, hwF, hadj0w⟩, hfort⟩  have h12 : 1 ∉ W ∨ 2 ∉ W := by    by_contra hc    push Not at hc    apply h    intro x hx    fin_cases x    · exfalso; revert hx; decide    · exact hc.1    · exact hc.2  cases h12 with  | inl h1W =>    have h1F : 1 ∉ F := fun h => h1W (hFW h)    have : w = 1 := by      rw [pathGraph_adj] at hadj0w      fin_cases w      · revert hadj0w; decide      · rfl      · revert hadj0w; decide    subst this    exact h1F hwF  | inr h2W =>    have h2F : 2 ∉ F := fun h => h2W (hFW h)    have hw1 : w = 1 := by      rw [pathGraph_adj] at hadj0w      fin_cases w      · revert hadj0w; decide      · rfl      · revert hadj0w; decide    have h2ne0 : (2 : Fin 3) ≠ 0 := by decide    have h2adj1 : (pathGraph 3).Adj 2 1 := by rw [pathGraph_adj]; decide    obtain ⟨x, hxF, hadj2x, hxnew⟩ := hfort 2 h2ne0 h2F w hwF (hw1 ▸ h2adj1)    have : x = 1 := by      have : x ≠ 0 := by        intro hx0        subst hx0        revert hadj2x        rw [pathGraph_adj]; decide      have : x ≠ 2 := fun hx2 => h2F (hx2 ▸ hxF)      fin_cases x      · contradiction      · rfl      · contradiction    apply hxnew    rw [hw1, this]lemma tree_exposure_plain_partial_sync_counterexample_finset_card_one (W : Finset (Fin 3)) (h : W.card = 1) :    W = {0} ∨ W = {1} ∨ W = {2} := by  obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp h  fin_cases x <;> simplemma tree_exposure_plain_partial_sync_counterexample_finset_card_two (W : Finset (Fin 3)) (h : W.card = 2) :    W = {0, 1} ∨ W = {0, 2} ∨ W = {1, 2} := by  have h1 : (Finset.univ \ W).card = 1 := by    rw [Finset.card_sdiff_of_subset (Finset.subset_univ W), Finset.card_univ, Fintype.card_fin, h]  obtain ⟨x, hx⟩ := Finset.card_eq_one.mp h1  have hw : W = Finset.univ \ {x} := by    have := Finset.sdiff_sdiff_eq_self (Finset.subset_univ W)    rw [hx] at this    exact this.symm  fin_cases x  · right; right; rw [hw]; decide  · right; left; rw [hw]; decide  · left; rw [hw]; decidelemma tree_exposure_plain_partial_sync_counterexample_isTree : (pathGraph 3).IsTree := by  rw [SimpleGraph.isTree_iff_connected_and_card]  refine ⟨SimpleGraph.pathGraph_connected 2, ?_⟩  rw [Nat.card_fin, Nat.card_eq_fintype_card, <- SimpleGraph.edgeFinset_card]  decidelemma tree_exposure_plain_partial_sync_counterexample_c_0_false : zero_forcing_root_exposure_count (pathGraph 3) 0 0 false = 1 := by  unfold zero_forcing_root_exposure_count  have : {W : Finset (Fin 3) | W.card = 0 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((false = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = {∅} := by    ext W    simp only [Set.mem_singleton_iff]    constructor    · rintro ⟨hcard, -⟩      exact Finset.card_eq_zero.mp hcard    · rintro rfl      refine ⟨rfl, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem ∅ (Or.inl (by decide)), ?_⟩      simp only [Bool.false_eq_true, false_iff]      apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset      decide  rw [this]  exact Set.ncard_singleton ∅lemma tree_exposure_plain_partial_sync_counterexample_c_0_true : zero_forcing_root_exposure_count (pathGraph 3) 0 0 true = 0 := by  unfold zero_forcing_root_exposure_count  have : {W : Finset (Fin 3) | W.card = 0 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ∅ := by    ext W    constructor    · rintro ⟨hcard, _, he⟩      have : W = ∅ := Finset.card_eq_zero.mp hcard      subst this      have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 ∅ := he.mp rfl      have hnot := tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset ∅ (by decide)      exact hnot hexp    · intro h      exact False.elim h  rw [this, Set.ncard_empty]lemma tree_exposure_plain_partial_sync_counterexample_c_1_true : zero_forcing_root_exposure_count (pathGraph 3) 0 1 true = 0 := by  unfold zero_forcing_root_exposure_count  have : {W : Finset (Fin 3) | W.card = 1 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ∅ := by    ext W    constructor    · rintro ⟨hcard, _, he⟩      have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 W := he.mp rfl      have hnot : ¬ zero_forcing_root_exposed_fort (pathGraph 3) 0 W := by        apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset        intro hsub        have hc : ({1, 2} : Finset (Fin 3)).card = 2 := by decide        have : ({1, 2} : Finset (Fin 3)).card ≤ W.card := Finset.card_le_card hsub        omega      exact hnot hexp    · intro h      exact False.elim h  rw [this, Set.ncard_empty]lemma tree_exposure_plain_partial_sync_counterexample_c_2_true : zero_forcing_root_exposure_count (pathGraph 3) 0 2 true = 1 := by  unfold zero_forcing_root_exposure_count  have : {W : Finset (Fin 3) | W.card = 2 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((true = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = {{1, 2}} := by    ext W    constructor    · rintro ⟨hcard, _, he⟩      have hexp : zero_forcing_root_exposed_fort (pathGraph 3) 0 W := he.mp rfl      obtain (h | h | h) := tree_exposure_plain_partial_sync_counterexample_finset_card_two W hcard      · exfalso        subst h        exact tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset {0, 1} (by decide) hexp      · exfalso        subst h        exact tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset {0, 2} (by decide) hexp      · exact Set.mem_singleton_iff.mpr h    · rintro rfl      refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {1, 2} (Or.inl (by decide)), ?_⟩      simp [tree_exposure_plain_partial_sync_counterexample_exposed_12]  rw [this, Set.ncard_singleton]lemma tree_exposure_plain_partial_sync_counterexample_c_1_false : zero_forcing_root_exposure_count (pathGraph 3) 0 1 false = 3 := by  unfold zero_forcing_root_exposure_count  have : {W : Finset (Fin 3) | W.card = 1 ∧ is_zero_forcing_set (pathGraph 3) ((Finset.univ \ W : Finset (Fin 3)) : Set (Fin 3)) ∧ ((false = true) ↔ zero_forcing_root_exposed_fort (pathGraph 3) 0 W)} = ({{0}, {1}, {2}} : Finset (Finset (Fin 3))) := by    ext W    simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]    constructor    · rintro ⟨hcard, _, _⟩      exact tree_exposure_plain_partial_sync_counterexample_finset_card_one W hcard    · rintro (rfl | rfl | rfl)      · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {0} (Or.inr (by decide)), ?_⟩        simp only [Bool.false_eq_true, false_iff]        apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide      · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {1} (Or.inl (by decide)), ?_⟩        simp only [Bool.false_eq_true, false_iff]        apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide      · refine ⟨by decide, tree_exposure_plain_partial_sync_counterexample_zf_of_not_mem {2} (Or.inl (by decide)), ?_⟩        simp only [Bool.false_eq_true, false_iff]        apply tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset; decide  rw [this, Set.ncard_coe_finset]  decidetheorem tree_exposure_plain_partial_sync_counterexample : ∃ (T : SimpleGraph (Fin 3)) (r : Fin 3), T.IsTree ∧ zero_forcing_root_exposure_count T r 0 false = 1 ∧ zero_forcing_root_exposure_count T r 1 false = 3 ∧ zero_forcing_root_exposure_count T r 0 true = 0 ∧ zero_forcing_root_exposure_count T r 1 true = 0 ∧ zero_forcing_root_exposure_count T r 2 true = 1 := by  refine ⟨pathGraph 3, 0, tree_exposure_plain_partial_sync_counterexample_isTree,    tree_exposure_plain_partial_sync_counterexample_c_0_false,    tree_exposure_plain_partial_sync_counterexample_c_1_false,    tree_exposure_plain_partial_sync_counterexample_c_0_true,    tree_exposure_plain_partial_sync_counterexample_c_1_true,    tree_exposure_plain_partial_sync_counterexample_c_2_true⟩
See it in the graphDiscuss this resultChallenge it