tree_exposure_plain_partial_sync_counterexample
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 nis 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.
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.
uses
pathGraph_adjlemma 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
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.
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_2lemma 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
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.
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_2lemma 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
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}.
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_twolemma 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
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.
uses
subset_rfl,pathGraph_adjlemma 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
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.
uses
pathGraph_adjlemma 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]
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}.
uses
Finset.card_eq_one.mplemma 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
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}.
uses
Finset.card_sdiff_of_subset,Finset.subset_univ,Finset.card_univ,Fintype.card_fin,Finset.card_eq_one.mp,Finset.sdiff_sdiff_eq_selflemma 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
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.
uses
SimpleGraph.isTree_iff_connected_and_card,SimpleGraph.pathGraph_connected,Nat.card_fin,Nat.card_eq_fintype_card,SimpleGraph.edgeFinset_cardlemma 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
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.
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_singletonlemma 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 ∅
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.
uses
Finset.card_eq_zero.mp,tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset,False.elim,Set.ncard_emptylemma 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]
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.
uses
tree_exposure_plain_partial_sync_counterexample_not_exposed_of_not_subset,Finset.card_le_card,False.elim,Set.ncard_emptylemma 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]
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.
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_singletonlemma 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]
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.
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_finsetlemma 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
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.
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_truetheorem 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
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.
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⟩