AFTD Auto-Formalizing Theoretical Domains

gt_connected_forcing_poly_eq

theoremverified

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.

  1. 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.

    lines 1–10

    uses congr_arg

    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.symm
  2. 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.

    lines 12–22

    uses False.elim

    lemma 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)
  3. 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.

    lines 24–32

    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
  4. 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.

    lines 33–42

    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 rfl
  5. Every 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.

    lines 44–60

    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
  6. 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.

    lines 62–72

    uses SimpleGraph.connected_iff_exists_forall_reachable, SimpleGraph.Reachable.refl, gt_connected_forcing_poly_eq_adj_R, SimpleGraph.Adj.reachable

    lemma 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
  7. 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.

    lines 74–78

    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
  8. 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.

    lines 79–89

    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
  9. 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.

    lines 92–97

    uses Finset.sum_congr, gt_connected_forcing_poly_eq_is_connected_forcing_set_iff_zero_forcing_set

    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]
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

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