szf_multigraph_closure_indicator
On a graph without parallel edges (multiplicities 0 or 1, given by neighbourhood sets N), the multigraph skew zero forcing closure coincides with the set-based skew zero forcing closure.
Statement
theorem szf_multigraph_closure_indicator {V : Type*} (N : V → Set V) [∀ u, DecidablePred (· ∈ N u)] (S : Set V) : szf_multigraph_closure (fun u v => if v ∈ N u then 1 else 0) S = skew_zero_forcing_closure N S
- Source
- sanity lemma for szf_multigraph_closure (arXiv:2611.15741 Section 1)
- Verified
- 15 Nov 2026
- Axioms
Quot.soundpropext- Built on 4
- szf_multigraph_closureThe skew zero forcing closure scl(S) of a vertex set S in the multigraph with adjacency multiplicities μ: the set of vertices forced from…
- skew_zero_forcing_closureThe skew zero forcing closure scl(S) of a subset S of vertices in a graph with neighborhood function N is the set of all vertices forced…
- SkewZeroForcedThe skew zero forcing closure predicate on vertices V: a vertex is forced from an initial set S under neighborhood function N if it is in…
- SzfMultiForcedSkew zero forcing on a multigraph with adjacency multiplicities μ (μ u v = number of edges between u and v, μ u u = number of loops at u):…
The proof, explained
The proof shows the equality of the two closures by set extensionality and mutual induction on the inductively defined forcing relations. Because the multigraph edge multiplicity is defined as the indicator function of the neighbourhood relation N, having multiplicity 1 is equivalent to being an adjacent vertex in N, and having non-zero multiplicity is likewise equivalent to adjacency. Consequently, the base cases and the forcing steps correspond bijectively between the multigraph and set-based definitions.
To prove the two closures are equal, it suffices to show that any vertex v belongs to the multigraph closure if and only if it belongs to the set-based closure.
By set extensionality, two sets are identical if they contain the same elements; this splits the proof into two inclusions.
ext v constructor
Any initial vertex v ∈ S belongs to the set-based closure.
For the forward inclusion, we proceed by induction on the derivation that v is forced in the multigraph. In the base case v ∈ S, the result holds immediately by SkewZeroForced.init.
uses
SkewZeroForced.init· intro h induction h with | init v hv => exact SkewZeroForced.init _ hv
If a vertex w is forced in the multigraph via u, then w is also forced in the set-based closure.
In the induction step, w was forced by u because the multiplicity μ(u, w) = 1, which means w ∈ N(u). For any other neighbour x ∈ N(u) with x ≠ w, the multiplicity μ(u, x) = 1 ≠ 0, so by the induction hypothesis x is already forced in the set-based closure. Hence w is forced by SkewZeroForced.step.
uses
SkewZeroForced.step| step u w huw hf ih => apply SkewZeroForced.step u w · simpa using huw · intro x hx hxw exact ih x hxw (by simp [hx])Any initial vertex v ∈ S belongs to the multigraph closure.
For the reverse inclusion, we proceed by induction on the derivation that v is forced in the set-based sense. In the base case v ∈ S, the result holds immediately by SzfMultiForced.init.
uses
SzfMultiForced.init· intro h induction h with | init v hv => exact SzfMultiForced.init _ hv
If a vertex w is forced in the set-based process via u, then w is also forced in the multigraph closure.
In the induction step, w ∈ N(u) implies the multiplicity μ(u, w) = 1. If any vertex x ≠ w has non-zero multiplicity μ(u, x) ≠ 0, then by definition x ∈ N(u), so by the induction hypothesis x is already multigraph-forced. Thus, the multigraph forcing rule SzfMultiForced.step applies to force w.
uses
SzfMultiForced.step| step u w hw hf ih => apply SzfMultiForced.step u w · simpa using hw · intro x hxw hxne exact ih x (by by_contra hx simp [hx] at hxne) hxw
SkewZeroForced.init- Every element of the initial set S is forced in the set-based skew zero forcing process.
SkewZeroForced.step- If w is a neighbour of u and all other neighbours of u are already forced, then w is forced in the set-based skew zero forcing process.
SzfMultiForced.init- Every element of the initial set S is forced in the multigraph skew zero forcing process.
SzfMultiForced.step- If the edge multiplicity between u and w is 1, and every other vertex connected to u by at least one edge is already forced, then w is forced in the multigraph skew zero forcing process.
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.
theorem szf_multigraph_closure_indicator {V : Type*} (N : V → Set V) [∀ u, DecidablePred (· ∈ N u)] (S : Set V) : szf_multigraph_closure (fun u v => if v ∈ N u then 1 else 0) S = skew_zero_forcing_closure N S := by ext v constructor · intro h induction h with | init v hv => exact SkewZeroForced.init _ hv | step u w huw hf ih => apply SkewZeroForced.step u w · simpa using huw · intro x hx hxw exact ih x hxw (by simp [hx]) · intro h induction h with | init v hv => exact SzfMultiForced.init _ hv | step u w hw hf ih => apply SzfMultiForced.step u w · simpa using hw · intro x hxw hxne exact ih x (by by_contra hx simp [hx] at hxne) hxw