univ_is_zero_forcing_set
The full set of vertices of any graph G is a zero forcing set.
Statement
theorem univ_is_zero_forcing_set {V : Type*} (G : SimpleGraph V) : is_zero_forcing_set G Set.univ
- Source
- arXiv:2611.11352 Section 1
- Verified
- 11 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- 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.
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
Read back from the Lean
For any type V and any simple graph G on V, the universal set Set.univ is a zero forcing set of G.
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
To show that the universal set of vertices is a zero forcing set, it suffices to show that every vertex in the graph is zero forced. Because every vertex trivially belongs to the universal set, each vertex is already forced at the initial step by the base case of the inductive definition of zero forcing.
Every vertex of the graph is zero forced by the universal set.
To show that the universal set is a zero forcing set, we must show that every vertex v is zero forced. An arbitrary vertex v belongs to the universal set by Set.mem_univ, and any vertex in the set is immediately zero forced by the base case constructor ZeroForced.init.
uses
ZeroForced.init,Set.mem_univintro v exact ZeroForced.init v (Set.mem_univ v)
ZeroForced.init- Any vertex belonging to the initial set S is zero forced from S.
Set.mem_univ- Every element of a type belongs to the universal set of that type.
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.
/-- Sanity lemma: the universal set is always a zero forcing set. -/theorem univ_is_zero_forcing_set {V : Type*} (G : SimpleGraph V) : is_zero_forcing_set G Set.univ := by intro v exact ZeroForced.init v (Set.mem_univ v)