gt_total_forcing_poly_eq
For every integer t ≥ 24, the total forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
Statement
theorem gt_total_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) :
total_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).
- total_forcing_polyGiven a finite type V and a simple graph G on V, total_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…
- is_total_forcing_setA total forcing set is a zero forcing set that induces a subgraph with no isolated vertices.
- 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.
- 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.
- 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 every natural number $t$ satisfying $t \ge 24$, the total forcing polynomial of the graph gt_graph t is equal to its zero forcing polynomial.
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
The total forcing polynomial and zero forcing polynomial of gt_graph t coincide for t ≥ 24 because every zero forcing set of the graph already induces a subgraph without isolated vertices, making the two classes of sets identical. The proof establishes a general fort lemma showing that vertices in a set whose external neighbors all have multiple connections into the set cannot be forced, which implies every zero forcing set has size at least 2 and must contain some vertex R i. Because every vertex except R i itself is adjacent to R i, every vertex in a zero forcing set has a neighbor within the set, so zero forcing sets are automatically total forcing sets. Comparing the two polynomials term by term across all vertex subsets completes the proof.
No vertex in a fort (a subset where every external neighbor has multiple connections into the set) can ever be zero forced from S.
We prove by induction on the derivation that v is zero forced from S that v cannot belong to W. In the base case, S and W are disjoint by hypothesis. In the inductive step, if u forces w ∈ W, then u cannot belong to W by the induction hypothesis for u; but if u ∉ W, by hypothesis u has another neighbor x ∈ W with x ≠ w, which must have been forced before w could be forced, contradicting the induction hypothesis for x. Hence no vertex in W is ever forced.
private lemma gt_total_forcing_poly_eq_stuck_notMem {V : Type*} {G : SimpleGraph V} {S W : Set V} (hSW : ∀ v, v ∈ S → v ∉ W) (hW : ∀ u, u ∉ W → ∀ w, w ∈ W → G.Adj u w → ∃ x, x ∈ W ∧ G.Adj u x ∧ x ≠ w) : ∀ v, v ∈ W → ¬ ZeroForced G S v := by have key : ∀ v, ZeroForced G S v → v ∈ W → False := by intro v hzf induction hzf with | init v hvS => intro hvW; exact hSW v hvS hvW | step u w hu hadj hstep ihu ihstep => intro hwW by_cases huw : u ∈ W · exact ihu huw · obtain ⟨x, hxW, hxadj, hxne⟩ := hW u huw w hwW hadj exact ihstep x hxadj hxne hxW intro v hvW hzf exact key v hzf hvW
In gt_graph t, every vertex u distinct from R i is adjacent to R i.
We check each vertex constructor (A, B, C, D, P, Q, R). Vertices of type A, B, C, D, P, Q are adjacent to all R vertices by definition of the graph. For an R vertex R i', the hypothesis u ≠ R i ensures i' ≠ i, and distinct R vertices are connected by an edge.
uses
Ne.symmprivate lemma gt_total_forcing_poly_eq_adj_to_R {t : ℕ} (i : Fin t) {u : GtVertex t} (hu : u ≠ GtVertex.R i) : (gt_graph t).Adj u (GtVertex.R i) := by cases u with | A i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | B i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | C i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | D i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | P i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | Q i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | R i' => have hne : i' ≠ i := fun h => hu (by rw [h]) simp [gt_graph, SimpleGraph.fromRel, gt_adj, hne, Ne.symm hne]
Distinct indices give distinct R vertices: i ≠ j implies R i ≠ R j.
If R i = R j, injectivity of the constructor GtVertex.R forces i = j, contradicting i ≠ j.
uses
GtVertex.R.injprivate lemma gt_total_forcing_poly_eq_R_ne_R {t : ℕ} {i j : Fin t} (h : i ≠ j) : (GtVertex.R i) ≠ (GtVertex.R j) := by intro hh; exact h (GtVertex.R.inj hh)
Every vertex in gt_graph t has at least two distinct neighbors.
Case analysis on the vertex type exhibits two explicit neighbors for each vertex: vertices of type A, C, P, Q, R are adjacent to B 0 and B 1; vertices of type B are adjacent to A 0 and A 1; and vertices of type D are adjacent to C 0 and C 1. In all cases, the two candidate neighbors are distinct.
private lemma gt_total_forcing_poly_eq_two_neighbors (t : ℕ) (v : GtVertex t) : ∃ a b, a ≠ b ∧ (gt_graph t).Adj v a ∧ (gt_graph t).Adj v b := by cases v with | A i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | B i => exact ⟨GtVertex.A 0, GtVertex.A 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | C i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | D i => exact ⟨GtVertex.C 0, GtVertex.C 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | P i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | Q i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | R i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩
For t ≥ 24, every zero forcing set of gt_graph t contains at least one R vertex.
Suppose for contradiction that S contains no R vertex. Then the set W of all R vertices is disjoint from S. Since t ≥ 24 > 1, for any outside neighbor u of R i ∈ W, there is another index j ≠ i; because u ∉ W, u ≠ R j, so u is also adjacent to R j ∈ W. Thus W is a fort, so no vertex in W can ever be forced from S. But S is a zero forcing set, so R 0 ∈ W must eventually be forced, a contradiction.
uses
Fintype.card_fin,Fintype.exists_ne_of_one_lt_card,Set.mem_range_self,gt_total_forcing_poly_eq_adj_to_R,gt_total_forcing_poly_eq_R_ne_R,gt_total_forcing_poly_eq_stuck_notMemprivate lemma gt_total_forcing_poly_eq_exists_R (t : ℕ) (ht : 24 ≤ t) {S : Set (GtVertex t)} (hS : is_zero_forcing_set (gt_graph t) S) : ∃ i : Fin t, GtVertex.R i ∈ S := by by_contra h push Not at h set W : Set (GtVertex t) := Set.range GtVertex.R with hWdef have hSW : ∀ v, v ∈ S → v ∉ W := by intro v hvS hvW obtain ⟨i, hi⟩ := hvW exact h i (hi ▸ hvS) have hstuck : ∀ u, u ∉ W → ∀ w, w ∈ W → (gt_graph t).Adj u w → ∃ x, x ∈ W ∧ (gt_graph t).Adj u x ∧ x ≠ w := by intro u huW w hwW _ obtain ⟨i, rfl⟩ := hwW have hcardt : 1 < Fintype.card (Fin t) := by rw [Fintype.card_fin]; omega obtain ⟨j, hji⟩ := Fintype.exists_ne_of_one_lt_card hcardt i have hune : u ≠ GtVertex.R j := fun hh => huW (hh ▸ Set.mem_range_self j) exact ⟨GtVertex.R j, Set.mem_range_self j, gt_total_forcing_poly_eq_adj_to_R j hune, gt_total_forcing_poly_eq_R_ne_R hji⟩ have hnotmem := gt_total_forcing_poly_eq_stuck_notMem hSW hstuck have hmem : (GtVertex.R (⟨0, by omega⟩ : Fin t)) ∈ W := Set.mem_range_self _ exact hnotmem _ hmem (hS _)
In any graph of minimum degree at least 2, every zero forcing set has cardinality at least 2.
If S had cardinality at most 1, its complement W would be a non-empty set disjoint from S. Any vertex u ∉ W belongs to S. Since u has at least two neighbors and |S| ≤ 1, none of its neighbors can be in S (as graphs have no self-loops, so a neighbor cannot equal u). Hence all neighbors of u lie in W. Thus u has at least two neighbors in W, so no neighbor w ∈ W can be forced by u. By the fort lemma, no vertex in W can be forced, contradicting that S is a zero forcing set.
uses
Finset.card_le_one.mp,gt_total_forcing_poly_eq_stuck_notMemprivate lemma gt_total_forcing_poly_eq_card_two_le {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] {G : SimpleGraph V} (hdeg : ∀ v, ∃ a b, a ≠ b ∧ G.Adj v a ∧ G.Adj v b) {S : Finset V} (hS : is_zero_forcing_set G (S : Set V)) : 2 ≤ S.card := by by_contra h push Not at h have hcle : S.card ≤ 1 := by omega have hpair : ∀ a ∈ S, ∀ b ∈ S, a = b := Finset.card_le_one.mp hcle have hSW : ∀ v, v ∈ (S : Set V) → v ∉ ((S : Set V)ᶜ) := by intro v hv hv' exact hv' hv have hstuck : ∀ u, u ∉ ((S : Set V)ᶜ) → ∀ w, w ∈ ((S : Set V)ᶜ) → G.Adj u w → ∃ x, x ∈ ((S : Set V)ᶜ) ∧ G.Adj u x ∧ x ≠ w := by intro u hu w _ hadj have huS : u ∈ S := by simpa using hu obtain ⟨a, b, hab, hua, hub⟩ := hdeg u have haS : a ∉ S := fun ha => (G.ne_of_adj hua) (hpair a ha u huS).symm have hbS : b ∉ S := fun hb => (G.ne_of_adj hub) (hpair b hb u huS).symm by_cases haw : a = w · exact ⟨b, by simpa using hbS, hub, by rw [← haw]; exact hab.symm⟩ · exact ⟨a, by simpa using haS, hua, haw⟩ have hWne : ∃ w, w ∈ ((S : Set V)ᶜ) := by obtain ⟨v⟩ := (inferInstance : Nonempty V) by_cases hv : v ∈ (S : Set V) · obtain ⟨a, b, hab, hua, hub⟩ := hdeg v exact ⟨a, by simpa using fun ha => (G.ne_of_adj hua) (hpair a ha v hv).symm⟩ · exact ⟨v, by simpa using hv⟩ obtain ⟨w, hw⟩ := hWne exact gt_total_forcing_poly_eq_stuck_notMem hSW hstuck w hw (hS w)
For t ≥ 24, every zero forcing set S of gt_graph t induces a subgraph with no isolated vertices.
Let S be a zero forcing set. By the previous lemmas, |S| ≥ 2 and there exists an index i such that R i ∈ S. For any vertex v ∈ S: if v ≠ R i, then v is adjacent to R i ∈ S by the universal adjacency lemma. If v = R i, since |S| ≥ 2 there exists another vertex w ∈ S with w ≠ R i, and R i is adjacent to w by symmetry. Thus every vertex in S has a neighbor in S.
uses
gt_total_forcing_poly_eq_card_two_le,gt_total_forcing_poly_eq_two_neighbors,gt_total_forcing_poly_eq_exists_R,Finset.card_le_one,gt_total_forcing_poly_eq_adj_to_Rprivate lemma gt_total_forcing_poly_eq_no_isolated (t : ℕ) (ht : 24 ≤ t) (S : Finset (GtVertex t)) (hS : is_zero_forcing_set (gt_graph t) (S : Set (GtVertex t))) : ∀ v : (S : Set (GtVertex t)), ∃ w : (S : Set (GtVertex t)), (gt_graph t).Adj (v : GtVertex t) (w : GtVertex t) := by haveI : Nonempty (GtVertex t) := ⟨GtVertex.A 0⟩ have hcard : 2 ≤ S.card := gt_total_forcing_poly_eq_card_two_le (gt_total_forcing_poly_eq_two_neighbors t) hS obtain ⟨i, hiS⟩ := gt_total_forcing_poly_eq_exists_R t ht hS intro v by_cases hv : (v : GtVertex t) = GtVertex.R i · have hother : ∃ w ∈ S, w ≠ GtVertex.R i := by by_contra hh push Not at hh have hle : S.card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb rw [hh a ha, hh b hb] omega obtain ⟨w, hwS, hwne⟩ := hother exact ⟨⟨w, hwS⟩, by rw [hv] exact (gt_total_forcing_poly_eq_adj_to_R i hwne).symm⟩ · exact ⟨⟨GtVertex.R i, hiS⟩, gt_total_forcing_poly_eq_adj_to_R i hv⟩
For t ≥ 24, the total forcing polynomial of gt_graph t equals its zero forcing polynomial.
Both polynomials are sums of X^|S| over subsets S satisfying the respective forcing property. By Finset.sum_congr, it suffices to show the terms match for every subset S. If S is a zero forcing set, it has no isolated vertices, so it is also a total forcing set; thus both summands are X^|S|. If S is not a zero forcing set, it cannot be a total forcing set (as total forcing implies zero forcing); thus both summands are 0. Hence the two polynomials are equal.
uses
Finset.sum_congr,gt_total_forcing_poly_eq_no_isolatedtheorem gt_total_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) : total_forcing_poly (gt_graph t) = zero_forcing_poly (gt_graph t) := by dsimp [total_forcing_poly, zero_forcing_poly] refine Finset.sum_congr rfl (fun S _ => ?_) by_cases h : is_zero_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) · have ht' : is_total_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) := ⟨h, gt_total_forcing_poly_eq_no_isolated t ht S h⟩ simp [h, ht'] · have ht' : ¬ is_total_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) := fun hh => h hh.1 simp [h, ht']
Finset.card_le_one.mp- If a finite set has cardinality at most 1, any two of its elements are equal.
Finset.card_le_one- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their terms agree on every element.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.exists_ne_of_one_lt_card- In any finite type with more than one element, every element has a distinct companion element.
GtVertex.R.inj- The constructor GtVertex.R is injective.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Set.mem_range_self- For any function f, f(i) belongs to the range of f.
gt_total_forcing_poly_eq_adj_to_R- In gt_graph t, any vertex distinct from R i is adjacent to R i.
gt_total_forcing_poly_eq_card_two_le- In a graph where every vertex has at least two neighbors, every zero forcing set has cardinality at least 2.
gt_total_forcing_poly_eq_exists_R- For t ≥ 24, every zero forcing set of gt_graph t contains at least one vertex of the form R i.
gt_total_forcing_poly_eq_no_isolated- For t ≥ 24, every zero forcing set of gt_graph t induces a subgraph with no isolated vertices.
gt_total_forcing_poly_eq_R_ne_R- Distinct indices i ≠ j produce distinct vertices R i ≠ R j.
gt_total_forcing_poly_eq_stuck_notMem- If W is disjoint from S and every outside neighbor of W has another neighbor in W, no vertex in W can be zero forced from S.
gt_total_forcing_poly_eq_two_neighbors- Every vertex in gt_graph t has at least two distinct neighbors.
- Adjacency relations in gt_graph t are verified by automated case analysis expanding the inductive definition of the vertex type and the graph's edge relation.
- The equivalence between polynomials is established via Finset.sum_congr, comparing the two sums term by term for each vertex subset.
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.
private lemma gt_total_forcing_poly_eq_stuck_notMem {V : Type*} {G : SimpleGraph V} {S W : Set V} (hSW : ∀ v, v ∈ S → v ∉ W) (hW : ∀ u, u ∉ W → ∀ w, w ∈ W → G.Adj u w → ∃ x, x ∈ W ∧ G.Adj u x ∧ x ≠ w) : ∀ v, v ∈ W → ¬ ZeroForced G S v := by have key : ∀ v, ZeroForced G S v → v ∈ W → False := by intro v hzf induction hzf with | init v hvS => intro hvW; exact hSW v hvS hvW | step u w hu hadj hstep ihu ihstep => intro hwW by_cases huw : u ∈ W · exact ihu huw · obtain ⟨x, hxW, hxadj, hxne⟩ := hW u huw w hwW hadj exact ihstep x hxadj hxne hxW intro v hvW hzf exact key v hzf hvWprivate lemma gt_total_forcing_poly_eq_adj_to_R {t : ℕ} (i : Fin t) {u : GtVertex t} (hu : u ≠ GtVertex.R i) : (gt_graph t).Adj u (GtVertex.R i) := by cases u with | A i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | B i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | C i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | D i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | P i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | Q i' => simp [gt_graph, SimpleGraph.fromRel, gt_adj] | R i' => have hne : i' ≠ i := fun h => hu (by rw [h]) simp [gt_graph, SimpleGraph.fromRel, gt_adj, hne, Ne.symm hne]private lemma gt_total_forcing_poly_eq_R_ne_R {t : ℕ} {i j : Fin t} (h : i ≠ j) : (GtVertex.R i) ≠ (GtVertex.R j) := by intro hh; exact h (GtVertex.R.inj hh)private lemma gt_total_forcing_poly_eq_two_neighbors (t : ℕ) (v : GtVertex t) : ∃ a b, a ≠ b ∧ (gt_graph t).Adj v a ∧ (gt_graph t).Adj v b := by cases v with | A i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | B i => exact ⟨GtVertex.A 0, GtVertex.A 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | C i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | D i => exact ⟨GtVertex.C 0, GtVertex.C 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | P i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | Q i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩ | R i => exact ⟨GtVertex.B 0, GtVertex.B 1, by simp, by simp [gt_graph, SimpleGraph.fromRel, gt_adj], by simp [gt_graph, SimpleGraph.fromRel, gt_adj]⟩private lemma gt_total_forcing_poly_eq_exists_R (t : ℕ) (ht : 24 ≤ t) {S : Set (GtVertex t)} (hS : is_zero_forcing_set (gt_graph t) S) : ∃ i : Fin t, GtVertex.R i ∈ S := by by_contra h push Not at h set W : Set (GtVertex t) := Set.range GtVertex.R with hWdef have hSW : ∀ v, v ∈ S → v ∉ W := by intro v hvS hvW obtain ⟨i, hi⟩ := hvW exact h i (hi ▸ hvS) have hstuck : ∀ u, u ∉ W → ∀ w, w ∈ W → (gt_graph t).Adj u w → ∃ x, x ∈ W ∧ (gt_graph t).Adj u x ∧ x ≠ w := by intro u huW w hwW _ obtain ⟨i, rfl⟩ := hwW have hcardt : 1 < Fintype.card (Fin t) := by rw [Fintype.card_fin]; omega obtain ⟨j, hji⟩ := Fintype.exists_ne_of_one_lt_card hcardt i have hune : u ≠ GtVertex.R j := fun hh => huW (hh ▸ Set.mem_range_self j) exact ⟨GtVertex.R j, Set.mem_range_self j, gt_total_forcing_poly_eq_adj_to_R j hune, gt_total_forcing_poly_eq_R_ne_R hji⟩ have hnotmem := gt_total_forcing_poly_eq_stuck_notMem hSW hstuck have hmem : (GtVertex.R (⟨0, by omega⟩ : Fin t)) ∈ W := Set.mem_range_self _ exact hnotmem _ hmem (hS _)private lemma gt_total_forcing_poly_eq_card_two_le {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] {G : SimpleGraph V} (hdeg : ∀ v, ∃ a b, a ≠ b ∧ G.Adj v a ∧ G.Adj v b) {S : Finset V} (hS : is_zero_forcing_set G (S : Set V)) : 2 ≤ S.card := by by_contra h push Not at h have hcle : S.card ≤ 1 := by omega have hpair : ∀ a ∈ S, ∀ b ∈ S, a = b := Finset.card_le_one.mp hcle have hSW : ∀ v, v ∈ (S : Set V) → v ∉ ((S : Set V)ᶜ) := by intro v hv hv' exact hv' hv have hstuck : ∀ u, u ∉ ((S : Set V)ᶜ) → ∀ w, w ∈ ((S : Set V)ᶜ) → G.Adj u w → ∃ x, x ∈ ((S : Set V)ᶜ) ∧ G.Adj u x ∧ x ≠ w := by intro u hu w _ hadj have huS : u ∈ S := by simpa using hu obtain ⟨a, b, hab, hua, hub⟩ := hdeg u have haS : a ∉ S := fun ha => (G.ne_of_adj hua) (hpair a ha u huS).symm have hbS : b ∉ S := fun hb => (G.ne_of_adj hub) (hpair b hb u huS).symm by_cases haw : a = w · exact ⟨b, by simpa using hbS, hub, by rw [← haw]; exact hab.symm⟩ · exact ⟨a, by simpa using haS, hua, haw⟩ have hWne : ∃ w, w ∈ ((S : Set V)ᶜ) := by obtain ⟨v⟩ := (inferInstance : Nonempty V) by_cases hv : v ∈ (S : Set V) · obtain ⟨a, b, hab, hua, hub⟩ := hdeg v exact ⟨a, by simpa using fun ha => (G.ne_of_adj hua) (hpair a ha v hv).symm⟩ · exact ⟨v, by simpa using hv⟩ obtain ⟨w, hw⟩ := hWne exact gt_total_forcing_poly_eq_stuck_notMem hSW hstuck w hw (hS w)private lemma gt_total_forcing_poly_eq_no_isolated (t : ℕ) (ht : 24 ≤ t) (S : Finset (GtVertex t)) (hS : is_zero_forcing_set (gt_graph t) (S : Set (GtVertex t))) : ∀ v : (S : Set (GtVertex t)), ∃ w : (S : Set (GtVertex t)), (gt_graph t).Adj (v : GtVertex t) (w : GtVertex t) := by haveI : Nonempty (GtVertex t) := ⟨GtVertex.A 0⟩ have hcard : 2 ≤ S.card := gt_total_forcing_poly_eq_card_two_le (gt_total_forcing_poly_eq_two_neighbors t) hS obtain ⟨i, hiS⟩ := gt_total_forcing_poly_eq_exists_R t ht hS intro v by_cases hv : (v : GtVertex t) = GtVertex.R i · have hother : ∃ w ∈ S, w ≠ GtVertex.R i := by by_contra hh push Not at hh have hle : S.card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb rw [hh a ha, hh b hb] omega obtain ⟨w, hwS, hwne⟩ := hother exact ⟨⟨w, hwS⟩, by rw [hv] exact (gt_total_forcing_poly_eq_adj_to_R i hwne).symm⟩ · exact ⟨⟨GtVertex.R i, hiS⟩, gt_total_forcing_poly_eq_adj_to_R i hv⟩/-- Total forcing polynomial of G_t equals its zero forcing polynomial. -/theorem gt_total_forcing_poly_eq (t : ℕ) (ht : 24 ≤ t) : total_forcing_poly (gt_graph t) = zero_forcing_poly (gt_graph t) := by dsimp [total_forcing_poly, zero_forcing_poly] refine Finset.sum_congr rfl (fun S _ => ?_) by_cases h : is_zero_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) · have ht' : is_total_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) := ⟨h, gt_total_forcing_poly_eq_no_isolated t ht S h⟩ simp [h, ht'] · have ht' : ¬ is_total_forcing_set (gt_graph t) (↑S : Set (GtVertex t)) := fun hh => h hh.1 simp [h, ht']