mem_petersen_strip_boundary
For a natural number k, a finite vertex set S : Finset PetersenStripVertex, and a vertex w : PetersenStripVertex, w ∈ petersen_strip_boundary k S if and only if w ∉ S and there exists some u ∈ S such that (petersen_strip k).Adj u w.
Statement
theorem mem_petersen_strip_boundary (k : ℕ) (S : Finset PetersenStripVertex) (w : PetersenStripVertex) : w ∈ petersen_strip_boundary k S ↔ w ∉ S ∧ ∃ u ∈ S, (petersen_strip k).Adj u w- Source
- scout/2610-24059-sharp-zero-forcing-numbers-for-the-generalized-petersen-gra.md:191
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- petersen_stripFor a natural number k,
petersen_strip kis the infinite simple graph with vertex setPetersenStripVertexwhere verticesu iand… - petersen_strip_boundaryFor a natural number k and a finite vertex set S : Finset PetersenStripVertex,
petersen_strip_boundary k Sis the… - PetersenStripVertexThe vertex set of the infinite generalized Petersen strip, consisting of outer vertices u_i and inner vertices v_i indexed by integers i…
- petersen_stripFor a natural number k,
- Used by 1
- petersen_strip_witness_boundary_cardFor each natural number k ≥ 8, the external boundary of petersen_strip_witness k has cardinality at most 2k + 1.
Read back from the Lean
For every natural number $k$, every finite set of vertices $S$ of type PetersenStripVertex, and every vertex $w$ of type PetersenStripVertex, $w$ is an element of petersen_strip_boundary k S if and only if $w \notin S$ and there exists some $u \in S$ such that $u$ is adjacent to $w$ in petersen_strip k.
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 external boundary of a vertex set S in the generalized Petersen strip is defined as the set difference (⋃_{u ∈ S} N(u)) \ S. The proof unfolds the definitions of set difference and indexed union, reducing the equivalence to showing that the neighborhood set N(u) matches the graph-theoretic neighbors under the adjacency relation of the Petersen strip. Both directions are then proved by exhaustive case analysis on whether u and w are outer vertices (u i) or inner vertices (v i).
The boundary membership condition w ∈ petersen_strip_boundary k S simplifies to w ∉ S and the existence of some u ∈ S such that w belongs to the neighborhood set defined for u.
Unfolding the definition of `petersen_strip_boundary`, the boundary is (⋃_{x ∈ S} N(x)) \ S. Rewriting with `Finset.mem_sdiff` and `Finset.mem_biUnion` expresses membership as w ∉ S together with the existence of some u ∈ S such that w is in the explicit neighborhood finset N(u). The `constructor` tactic then splits the equivalence into forward and reverse implications.
uses
Finset.mem_sdiff,Finset.mem_biUniondsimp only [petersen_strip_boundary] rw [Finset.mem_sdiff, Finset.mem_biUnion] constructor
In the forward direction, extracting the witness u ∈ S leaves the obligation to show that w ∈ N(u) implies adjacency of u and w in the Petersen strip.
Assuming w ∉ S and w ∈ N(u) for some u ∈ S, we provide w ∉ S and witness u ∈ S to match the goal w ∉ S ∧ ∃ u ∈ S, Adj u w. This reduces the forward direction to showing (petersen_strip k).Adj u w from w ∈ N(u).
· rintro ⟨⟨u, huS, huw⟩, hwS⟩ refine ⟨hwS, u, huS, ?_⟩In all four combinations of vertex types for u and w, membership w ∈ N(u) implies (petersen_strip k).Adj u w.
We split into cases based on whether u and w are outer vertices (u i, u j) or inner vertices (v i, v j): 1. Both outer (u i, u j): w ∈ {u (i+1), u (i-1), v i} simplifies via `Finset.mem_insert` and `Finset.mem_singleton` to j = i + 1 ∨ j = i - 1, matching outer-strip adjacency. 2. Outer-inner (u i, v j): w ∈ {u (i+1), u (i-1), v i} forces j = i, matching rung adjacency. 3. Inner-outer (v i, u j): whether k = 0 (where N(v i) = {u i}) or k ≠ 0 (where N(v i) = {u i, v (i+k), v (i-k)}), w = u j forces j = i, matching rung adjacency. 4. Both inner (v i, v j): if k = 0, N(v i) contains only u i, contradicting w = v j; if k ≠ 0, w ∈ {u i, v (i+k), v (i-k)} forces j = i + k ∨ j = i - k, matching inner-strip adjacency.
uses
Finset.mem_insert,Finset.mem_singletonrcases u with i | i <;> rcases w with j | j · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs at huw with hk · simp only [Finset.mem_singleton] at huw simp at huw ⊢ exact huw · simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs at huw with hk · simp only [Finset.mem_singleton] at huw contradiction · simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp [hk] at huw ⊢ exact huw
In the reverse direction, assuming w ∉ S and that w is adjacent to some u ∈ S, it suffices to show that w belongs to the neighborhood set N(u).
Introducing the hypotheses w ∉ S and u ∈ S with (petersen_strip k).Adj u w, we supply u as the witness for the indexed union and retain w ∉ S. The remaining goal is to show that adjacency implies w ∈ N(u).
· rintro ⟨hwS, u, huS, huw⟩ refine ⟨⟨u, huS, ?_⟩, hwS⟩In all four combinations of vertex types for u and w, adjacency (petersen_strip k).Adj u w implies w ∈ N(u).
We split into the four vertex-type cases: 1. Both outer (u i, u j): adjacency gives j = i + 1 ∨ j = i - 1, placing u j into {u (i+1), u (i-1), v i}. 2. Outer-inner (u i, v j): adjacency gives j = i, placing v j into {u (i+1), u (i-1), v i}. 3. Inner-outer (v i, u j): adjacency gives j = i. Whether k = 0 or k ≠ 0, this places u j into N(v i). 4. Both inner (v i, v j): adjacency gives k ≠ 0 and j = i + k ∨ j = i - k. The case k = 0 contradicts k ≠ 0, while for k ≠ 0 the index relation places v j into {u i, v (i+k), v (i-k)}. Each case simplifies using `Finset.mem_insert` and `Finset.mem_singleton` to complete the reverse implication.
uses
Finset.mem_insert,Finset.mem_singletonrcases u with i | i <;> rcases w with j | j · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs with hk · simp only [Finset.mem_singleton] simp at huw ⊢ exact huw · simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs with hk · subst hk simp at huw · simp only [Finset.mem_insert, Finset.mem_singleton] simp [hk] at huw ⊢ exact huw
Finset.mem_sdiff- An element belongs to the difference of two finite sets s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_biUnion- An element belongs to the union of a family of finite sets indexed by s if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
- The definition `petersen_strip_boundary` constructs the neighborhood of a vertex by explicit pattern matching on vertex constructors rather than referencing `(petersen_strip k).Adj` or graph-theoretic neighborhood functions. The proof therefore manually checks that this syntactic neighborhood definition matches the graph adjacency across all combinations of vertex types.
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.
/-- Characterization of the external vertex boundary in the generalized Petersen strip. -/theorem mem_petersen_strip_boundary (k : ℕ) (S : Finset PetersenStripVertex) (w : PetersenStripVertex) : w ∈ petersen_strip_boundary k S ↔ w ∉ S ∧ ∃ u ∈ S, (petersen_strip k).Adj u w := by dsimp only [petersen_strip_boundary] rw [Finset.mem_sdiff, Finset.mem_biUnion] constructor · rintro ⟨⟨u, huS, huw⟩, hwS⟩ refine ⟨hwS, u, huS, ?_⟩ rcases u with i | i <;> rcases w with j | j · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs at huw with hk · simp only [Finset.mem_singleton] at huw simp at huw ⊢ exact huw · simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs at huw with hk · simp only [Finset.mem_singleton] at huw contradiction · simp only [Finset.mem_insert, Finset.mem_singleton] at huw simp [hk] at huw ⊢ exact huw · rintro ⟨hwS, u, huS, huw⟩ refine ⟨⟨u, huS, ?_⟩, hwS⟩ rcases u with i | i <;> rcases w with j | j · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs with hk · simp only [Finset.mem_singleton] simp at huw ⊢ exact huw · simp only [Finset.mem_insert, Finset.mem_singleton] simp at huw ⊢ exact huw · dsimp [petersen_strip] at * split_ifs with hk · subst hk simp at huw · simp only [Finset.mem_insert, Finset.mem_singleton] simp [hk] at huw ⊢ exact huw