gt_connected_forcing_poly_eq
For every integer t ≥ 24, the connected forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
Statement
theorem gt_connected_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) :
connected_forcing_poly (gt_graph t) = zero_forcing_poly (gt_graph t)- Source
- arXiv:2611.11352 Corollary 2
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- gt_graphThe simple graph gt_graph t on vertex type GtVertex t, defined as SimpleGraph.fromRel (gt_adj t).
- connected_forcing_polyGiven a finite type V and a simple graph G on V, connected_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all…
- zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…
- GtVertexThe vertex set of the graph G_t partitioned into blocks A (size 3), B (size 2), C (size 2), D (size 3), P (size t), Q (size t), and R…
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
- is_connected_forcing_setA connected forcing set is a zero forcing set that induces a connected subgraph.
- 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.
- gt_adjThe adjacency relation gt_adj t on GtVertex t: vertices u and v are adjacent if and only if (u is in A and v is in B, or vice versa), (u…
Read back from the Lean
For any natural number $t$ such that $t \ge 24$, the connected forcing polynomial of the graph gt_graph t is equal to the zero forcing polynomial of gt_graph t.
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
Both polynomials are defined as sums over all vertex subsets S of X^|S|, filtering for connected forcing sets and zero forcing sets respectively. The two polynomials coincide for t ≥ 24 because every zero forcing set of G_t is already connected. This follows from the structure of G_t: each vertex of class R is adjacent to all other vertices, so containing any R vertex guarantees that the induced subgraph is connected; conversely, any set containing no R vertices can never force any R vertex during zero forcing, so every zero forcing set must contain at least one R vertex.
For t ≥ 2, every index i in Fin t has a distinct index k in Fin t.
We split into cases depending on whether i = 0. If i = 0, we select k = 1 (which is valid since t ≥ 2), and 1 ≠ 0. If i ≠ 0, we choose k = 0, which is distinct from i by assumption.
uses
congr_arglemma gt_connected_forcing_poly_eq_exists_ne_fin (t : ℕ) (ht : 2 ≤ t) (i : Fin t) : ∃ k : Fin t, k ≠ i := by by_cases h : i = ⟨0, by omega⟩ · use ⟨1, by omega⟩ intro heq have : (⟨1, by omega⟩ : Fin t).val = i.val := congr_arg Fin.val heq subst h norm_num at this · use ⟨0, by omega⟩ intro heq exact h heq.symm
Any vertex u not belonging to the R class is adjacent to R(k) for every k.
By definition of adjacency in G_t, we examine the constructor of vertex u. Vertices of types A, B, C, D, P, and Q are each connected to all R vertices by the construction of the graph. The remaining case u = R(j) contradicts the hypothesis that u is not in class R.
uses
False.elimlemma gt_connected_forcing_poly_eq_adj_R_of_not_R (t : ℕ) (u : GtVertex t) (h : ∀ j, u ≠ GtVertex.R j) (k : Fin t) : (gt_graph t).Adj u (GtVertex.R k) := by dsimp [gt_graph, SimpleGraph.fromRel] cases u with | A _ => simp [gt_adj] | B _ => simp [gt_adj] | C _ => simp [gt_adj] | D _ => simp [gt_adj] | P _ => simp [gt_adj] | Q _ => simp [gt_adj] | R j => exact False.elim (h j rfl)
If S contains no R vertices, no initially forced vertex belongs to class R.
We proceed by induction on the derivation that v is zero-forced from S. In the base case, v is an element of S. If v were of the form R(i), this would directly contradict the hypothesis that S contains no vertices of class R.
lemma gt_connected_forcing_poly_eq_not_zeroForced_R {t : ℕ} (ht : 2 ≤ t) {S : Set (GtVertex t)} (hS : ∀ i : Fin t, GtVertex.R i ∉ S) : ∀ v, ZeroForced (gt_graph t) S v → ∀ i : Fin t, v ≠ GtVertex.R i := by intro v hv induction hv with | init u hu => intro i heq subst heq exact hS i hu
Zero forcing from a set S containing no R vertices cannot force any R vertex.
Suppose for contradiction that an already forced vertex u forces a neighbor w = R(i). By the induction hypothesis, u cannot belong to class R. Since t ≥ 2, there exists an index k ≠ i, and because u is not of class R, u is adjacent to R(k). Since k ≠ i, R(k) is a neighbor of u distinct from w, so by the zero forcing rule, R(k) must have already been forced before this step. However, the induction hypothesis on all previously forced vertices states that no R vertex has been forced, a contradiction.
uses
gt_connected_forcing_poly_eq_exists_ne_fin,gt_connected_forcing_poly_eq_adj_R_of_not_R| step u w hu hadj hall ihu ihall => intro i heq subst heq obtain ⟨k, hk⟩ := gt_connected_forcing_poly_eq_exists_ne_fin t ht i have hadj_k : (gt_graph t).Adj u (GtVertex.R k) := gt_connected_forcing_poly_eq_adj_R_of_not_R t u ihu k have hne_k : GtVertex.R k ≠ GtVertex.R i := by intro heq injection heq with heq' exact hk heq' exact ihall (GtVertex.R k) hadj_k hne_k k rflEvery vertex R(i) is adjacent to every vertex v distinct from itself.
We inspect the type of v. If v belongs to classes A, B, C, D, P, or Q, it is adjacent to R(i) directly by the definition of the graph. If v = R(j), the hypothesis R(i) ≠ R(j) implies i ≠ j, which is precisely the adjacency condition between vertices of the R class.
lemma gt_connected_forcing_poly_eq_adj_R (t : ℕ) (i : Fin t) (v : GtVertex t) (h : GtVertex.R i ≠ v) : (gt_graph t).Adj (GtVertex.R i) v := by dsimp [gt_graph, SimpleGraph.fromRel] cases v with | A _ => simp [gt_adj] | B _ => simp [gt_adj] | C _ => simp [gt_adj] | D _ => simp [gt_adj] | P _ => simp [gt_adj] | Q _ => simp [gt_adj] | R j => simp only [gt_adj] have : i ≠ j := by intro heq subst heq exact h rfl tauto
If S contains any vertex R(i), the induced subgraph G[S] is connected.
A graph is connected if every vertex is reachable from some fixed vertex. Choosing R(i) ∈ S, any other vertex w ∈ S is either equal to R(i) (hence reachable in 0 steps) or distinct from R(i). When distinct, w is directly adjacent to R(i), meaning every vertex in S is reachable from R(i) in at most one step.
uses
SimpleGraph.connected_iff_exists_forall_reachable,SimpleGraph.Reachable.refl,gt_connected_forcing_poly_eq_adj_R,SimpleGraph.Adj.reachablelemma gt_connected_forcing_poly_eq_connected_induce_of_mem_R {t : ℕ} {S : Set (GtVertex t)} (i : Fin t) (hi : GtVertex.R i ∈ S) : ((gt_graph t).induce S).Connected := by rw [SimpleGraph.connected_iff_exists_forall_reachable] use ⟨GtVertex.R i, hi⟩ rintro ⟨w, hw⟩ by_cases h : GtVertex.R i = w · subst h exact SimpleGraph.Reachable.refl _ · have hadj : (gt_graph t).Adj (GtVertex.R i) w := gt_connected_forcing_poly_eq_adj_R t i w h exact SimpleGraph.Adj.reachable hadj
Every connected forcing set is a zero forcing set.
By definition, a connected forcing set is a zero forcing set whose induced subgraph is connected, so the forward implication holds immediately.
lemma gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set (t : ℕ) (ht : 24 ≤ t) (S : Set (GtVertex t)) : is_connected_forcing_set (gt_graph t) S ↔ is_zero_forcing_set (gt_graph t) S := by constructor · intro h exact h.1
For t ≥ 24, every zero forcing set is a connected forcing set.
Given a zero forcing set S, we show the induced subgraph G[S] is connected by contradiction. If G[S] were not connected, S could not contain any vertex R(i), since the presence of any R vertex makes G[S] connected. But if S contains no R vertices, then because t ≥ 24 ≥ 2, no vertex of class R could ever be zero-forced from S. This contradicts the fact that S forces every vertex in G_t, which includes R(0) since t ≥ 24 > 0.
uses
gt_connected_forcing_poly_eq_connected_induce_of_mem_R,gt_connected_forcing_poly_eq_not_zeroForced_R· intro h refine ⟨h, ?_⟩ by_contra hc have h_no_R : ∀ i : Fin t, GtVertex.R i ∉ S := by intro i hi exact hc (gt_connected_forcing_poly_eq_connected_induce_of_mem_R i hi) have ht2 : 2 ≤ t := by omega have h_not := gt_connected_forcing_poly_eq_not_zeroForced_R ht2 h_no_R have h0 : (0 : ℕ) < t := by omega have h_forced := h (GtVertex.R ⟨0, h0⟩) exact h_not (GtVertex.R ⟨0, h0⟩) h_forced ⟨0, h0⟩ rfl
For t ≥ 24, the connected forcing polynomial of G_t equals its zero forcing polynomial.
Both polynomials are defined as sums of X^|S| over all vertex subsets S satisfying the respective forcing property. For t ≥ 24, a subset is a connected forcing set if and only if it is a zero forcing set, so the summands agree for every subset S and the sums are equal.
uses
Finset.sum_congr,gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_settheorem gt_connected_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) : connected_forcing_poly (gt_graph t) = zero_forcing_poly (gt_graph t) := by dsimp [connected_forcing_poly, zero_forcing_poly] apply Finset.sum_congr rfl intro S _ rw [gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set t ht]
congr_arg- Applying a function to equal arguments yields equal results (if x = y then f x = f y).
False.elim- From a contradiction (False), any conclusion follows.
gt_connected_forcing_poly_eq_exists_ne_fin- For any t ≥ 2 and any index i in Fin t, there exists an index k in Fin t distinct from i.
gt_connected_forcing_poly_eq_adj_R_of_not_R- Any vertex u of G_t not belonging to the R class is adjacent to R(k) for all indices k.
gt_connected_forcing_poly_eq_adj_R- Every vertex R(i) in G_t is adjacent to every vertex v distinct from R(i).
SimpleGraph.connected_iff_exists_forall_reachable- A simple graph is connected if and only if there exists a vertex from which every vertex is reachable.
SimpleGraph.Reachable.refl- Every vertex in a graph is reachable from itself.
SimpleGraph.Adj.reachable- If two vertices in a graph are adjacent, each is reachable from the other.
gt_connected_forcing_poly_eq_connected_induce_of_mem_R- If a vertex set S in G_t contains any vertex R(i), then the induced subgraph on S is connected.
gt_connected_forcing_poly_eq_not_zeroForced_R- If t ≥ 2 and a subset S contains no vertices of the R class, then no vertex of the R class is ever zero-forced from S.
Finset.sum_congr- Two sums over the same finite set are equal if their terms agree on every element.
gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set- For t ≥ 24, a vertex subset S of G_t is a connected forcing set if and only if it is a zero forcing set.
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.
lemma gt_connected_forcing_poly_eq_exists_ne_fin (t : ℕ) (ht : 2 ≤ t) (i : Fin t) : ∃ k : Fin t, k ≠ i := by by_cases h : i = ⟨0, by omega⟩ · use ⟨1, by omega⟩ intro heq have : (⟨1, by omega⟩ : Fin t).val = i.val := congr_arg Fin.val heq subst h norm_num at this · use ⟨0, by omega⟩ intro heq exact h heq.symmlemma gt_connected_forcing_poly_eq_adj_R_of_not_R (t : ℕ) (u : GtVertex t) (h : ∀ j, u ≠ GtVertex.R j) (k : Fin t) : (gt_graph t).Adj u (GtVertex.R k) := by dsimp [gt_graph, SimpleGraph.fromRel] cases u with | A _ => simp [gt_adj] | B _ => simp [gt_adj] | C _ => simp [gt_adj] | D _ => simp [gt_adj] | P _ => simp [gt_adj] | Q _ => simp [gt_adj] | R j => exact False.elim (h j rfl)lemma gt_connected_forcing_poly_eq_not_zeroForced_R {t : ℕ} (ht : 2 ≤ t) {S : Set (GtVertex t)} (hS : ∀ i : Fin t, GtVertex.R i ∉ S) : ∀ v, ZeroForced (gt_graph t) S v → ∀ i : Fin t, v ≠ GtVertex.R i := by intro v hv induction hv with | init u hu => intro i heq subst heq exact hS i hu | step u w hu hadj hall ihu ihall => intro i heq subst heq obtain ⟨k, hk⟩ := gt_connected_forcing_poly_eq_exists_ne_fin t ht i have hadj_k : (gt_graph t).Adj u (GtVertex.R k) := gt_connected_forcing_poly_eq_adj_R_of_not_R t u ihu k have hne_k : GtVertex.R k ≠ GtVertex.R i := by intro heq injection heq with heq' exact hk heq' exact ihall (GtVertex.R k) hadj_k hne_k k rfllemma gt_connected_forcing_poly_eq_adj_R (t : ℕ) (i : Fin t) (v : GtVertex t) (h : GtVertex.R i ≠ v) : (gt_graph t).Adj (GtVertex.R i) v := by dsimp [gt_graph, SimpleGraph.fromRel] cases v with | A _ => simp [gt_adj] | B _ => simp [gt_adj] | C _ => simp [gt_adj] | D _ => simp [gt_adj] | P _ => simp [gt_adj] | Q _ => simp [gt_adj] | R j => simp only [gt_adj] have : i ≠ j := by intro heq subst heq exact h rfl tautolemma gt_connected_forcing_poly_eq_connected_induce_of_mem_R {t : ℕ} {S : Set (GtVertex t)} (i : Fin t) (hi : GtVertex.R i ∈ S) : ((gt_graph t).induce S).Connected := by rw [SimpleGraph.connected_iff_exists_forall_reachable] use ⟨GtVertex.R i, hi⟩ rintro ⟨w, hw⟩ by_cases h : GtVertex.R i = w · subst h exact SimpleGraph.Reachable.refl _ · have hadj : (gt_graph t).Adj (GtVertex.R i) w := gt_connected_forcing_poly_eq_adj_R t i w h exact SimpleGraph.Adj.reachable hadjlemma gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set (t : ℕ) (ht : 24 ≤ t) (S : Set (GtVertex t)) : is_connected_forcing_set (gt_graph t) S ↔ is_zero_forcing_set (gt_graph t) S := by constructor · intro h exact h.1 · intro h refine ⟨h, ?_⟩ by_contra hc have h_no_R : ∀ i : Fin t, GtVertex.R i ∉ S := by intro i hi exact hc (gt_connected_forcing_poly_eq_connected_induce_of_mem_R i hi) have ht2 : 2 ≤ t := by omega have h_not := gt_connected_forcing_poly_eq_not_zeroForced_R ht2 h_no_R have h0 : (0 : ℕ) < t := by omega have h_forced := h (GtVertex.R ⟨0, h0⟩) exact h_not (GtVertex.R ⟨0, h0⟩) h_forced ⟨0, h0⟩ rfl/-- Connected forcing polynomial of G_t equals its zero forcing polynomial. -/theorem gt_connected_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) : connected_forcing_poly (gt_graph t) = zero_forcing_poly (gt_graph t) := by dsimp [connected_forcing_poly, zero_forcing_poly] apply Finset.sum_congr rfl intro S _ rw [gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set t ht]