petersen_strip_witness_boundary_card
For each natural number k ≥ 8, the external boundary of petersen_strip_witness k has cardinality at most 2k + 1.
Statement
theorem petersen_strip_witness_boundary_card (k : ℕ) (hk : 8 ≤ k) : (petersen_strip_boundary k (petersen_strip_witness k)).card ≤ 2 * k + 1- Source
- step towards petersen_strip_small_boundary_attainment
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- petersen_strip_witnessExplicit finite vertex set witness achieving the quadratic bound k^2/2 + 1 with external boundary at most 2k + 1 in the generalized…
- petersen_strip_boundaryFor a natural number k and a finite vertex set S : Finset PetersenStripVertex,
petersen_strip_boundary k Sis the… - mem_petersen_strip_boundaryFor a natural number k, a finite vertex set S : Finset PetersenStripVertex, and a vertex w : PetersenStripVertex, w ∈…
- 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,
petersen_strip kis the infinite simple graph with vertex setPetersenStripVertexwhere verticesu iand…
- Used by 1
- petersen_strip_small_boundary_attainmentFor each natural number k ≥ 8, there exists a finite vertex set S in the generalized Petersen strip such that its boundary card is at most…
The proof, explained
The proof bounds the external boundary of the witness set S in the generalized Petersen strip by constructing an explicit superset B of candidate boundary vertices and bounding its cardinality. The witness set S consists of u-vertices on R disjoint blocks U of length m = ⌊k/2⌋ and v-vertices on V = U ∪ {extra}, where R + m = k. Any boundary vertex adjacent to S must fall into one of a few boundary shifts along the path or jump edges; analyzing these cases shows the boundary is contained in B = u(Bu) ∪ v(Bv). Finally, counting the elements shows |Bu| ≤ 2R + 1 and |Bv| ≤ 2m, giving |B| ≤ 2(R + m) + 1 = 2k + 1.
Define the witness set S explicitly as u(U) ∪ v(V) and rewrite the boundary goal in terms of S.
We set m = ⌊k / 2⌋ and R = m if k is even, or m + 1 if k is odd. The set U consists of R blocks of length m along the strip, spaced by k: U = ⋃_{r < R} { r*k + j | j < m }. The set V adds a single element, extra = R*k + m - 1, to U. The witness set S is defined as the union of u-vertices on U and v-vertices on V. Unfolding petersen_strip_witness verifies that it equals S, allowing us to rewrite the goal.
set m : ℕ := k / 2 with hm set R : ℕ := (if (k % 2 == 0) = true then m else m + 1) with hR set U : Finset ℤ := (Finset.range R).biUnion (fun r => Finset.image (fun j => (↑(r*k+j) : ℤ)) (Finset.range m)) with hU set extra : ℤ := (↑R : ℤ) * ↑k + ↑m - 1 with hextra set V : Finset ℤ := insert extra U with hV set S : Finset PetersenStripVertex := Finset.image PetersenStripVertex.u U ∪ Finset.image PetersenStripVertex.v V with hSdef have hS : petersen_strip_witness k = S := by rw [hSdef] unfold petersen_strip_witness simp only [← hm, ← hR, ← hU, ← hextra, ← hV] rw [hS]
The parameters satisfy m ≥ 4, m ≥ 1, R ≥ 1, and crucially R + m = k.
From k ≥ 8 and m = k / 2, linear integer arithmetic gives m ≥ 4 and m ≥ 1, and R ≥ 1 follows from R being either m or m + 1. To prove R + m = k, we perform a case split on the parity of k using Nat.mod_two_eq_zero_or_one: if k is even, R = m = k / 2 via if_pos, so m + m = k; if k is odd, R = m + 1 = k / 2 + 1 via if_neg, so (k / 2 + 1) + k / 2 = k.
uses
Nat.mod_two_eq_zero_or_one,if_pos,if_neghave hm4 : 4 ≤ m := by rw [hm]; omega have hm1 : 1 ≤ m := by omega have hR1 : 1 ≤ R := by rw [hR]; split_ifs <;> omega have hRk : R + m = k := by have h2 : k % 2 = 0 ∨ k % 2 = 1 := Nat.mod_two_eq_zero_or_one k rw [hR, hm] rcases h2 with h2 | h2 · have hb : (k % 2 == 0) = true := by simpa using h2 rw [if_pos hb]; omega · have hb : ¬ ((k % 2 == 0) = true) := by simp [h2] rw [if_neg hb]; omega
Define candidate boundary sets Bu, Bv, and B = u(Bu) ∪ v(Bv).
We define the candidates for boundary indices. For u-vertices, A1 contains the elements immediately to the right of each block of U (r*k + m for r < R), and A2 contains the elements immediately to the left of each block (r*k - 1 for r < R). Together with extra, these form Bu = A1 ∪ A2 ∪ {extra}. For v-vertices, C1 contains the upward shifts of the top block (R*k + j for j < m - 1, excluding extra), C3 contains the downward shifts of the bottom block (j - k for j < m), and together with extra + k, these form Bv = C1 ∪ {extra + k} ∪ C3. The candidate superset B is the union of u(Bu) and v(Bv).
set A1 : Finset ℤ := Finset.image (fun r => (↑(r*k+m) : ℤ)) (Finset.range R) with hA1 set A2 : Finset ℤ := Finset.image (fun r => (↑(r*k) : ℤ) - 1) (Finset.range R) with hA2 set C1 : Finset ℤ := Finset.image (fun j => (↑R : ℤ) * ↑k + ↑j) (Finset.range (m-1)) with hC1 set C3 : Finset ℤ := Finset.image (fun (j : ℕ) => (↑j : ℤ) - ↑k) (Finset.range m) with hC3 set Bu : Finset ℤ := A1 ∪ A2 ∪ {extra} with hBu set Bv : Finset ℤ := C1 ∪ {extra + ↑k} ∪ C3 with hBv set B : Finset PetersenStripVertex := Finset.image PetersenStripVertex.u Bu ∪ Finset.image PetersenStripVertex.v Bv with hB
Establish membership characterizations for U, S, and inclusion into B.
We characterize membership in U as being of the form r*k + j with r < R and j < m using Finset.mem_biUnion and Finset.mem_image. We then show that u(i) ∈ S ↔ i ∈ U and v(i) ∈ S ↔ i ∈ V using Finset.mem_union. We also prove convenient inclusion lemmas: elements of A1, A2, or {extra} belong to Bu, elements of C1, {extra + k}, or C3 belong to Bv, and any u-vertex with index in Bu or v-vertex with index in Bv belongs to B, via Finset.mem_union_left, Finset.mem_union_right, and Finset.mem_singleton_self.
uses
Finset.mem_biUnion,Finset.mem_image,Finset.mem_union,Finset.mem_union_left,Finset.mem_union_right,Finset.mem_singleton_selfhave hUmem : ∀ i : ℤ, i ∈ U ↔ ∃ r ∈ Finset.range R, ∃ j ∈ Finset.range m, i = (↑(r*k+j) : ℤ) := by intro i rw [hU] simp only [Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨r, hr, j, hj, hji⟩; exact ⟨r, hr, j, hj, hji.symm⟩ · rintro ⟨r, hr, j, hj, hij⟩; exact ⟨r, hr, j, hj, hij.symm⟩ have huS : ∀ i, (PetersenStripVertex.u i ∈ S) ↔ i ∈ U := by intro i; rw [hSdef] simp only [Finset.mem_union, Finset.mem_image] constructor · rintro (⟨i', hi', he⟩ | ⟨i', hi', he⟩) · cases he; exact hi' · exact absurd he (by simp) · intro hi; exact Or.inl ⟨i, hi, rfl⟩ have hvS : ∀ i, (PetersenStripVertex.v i ∈ S) ↔ i ∈ V := by intro i; rw [hSdef] simp only [Finset.mem_union, Finset.mem_image] constructor · rintro (⟨i', hi', he⟩ | ⟨i', hi', he⟩) · exact absurd he (by simp) · cases he; exact hi' · intro hi; exact Or.inr ⟨i, hi, rfl⟩ have hmemB_u : ∀ j : ℤ, j ∈ Bu → PetersenStripVertex.u j ∈ B := by intro j hj; rw [hB]; exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨j, hj, rfl⟩) have hmemB_v : ∀ j : ℤ, j ∈ Bv → PetersenStripVertex.v j ∈ B := by intro j hj; rw [hB]; exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨j, hj, rfl⟩) have htoBu_A1 : ∀ x : ℤ, x ∈ A1 → x ∈ Bu := by intro x hx; rw [hBu]; exact Finset.mem_union_left _ (Finset.mem_union_left _ hx) have htoBu_A2 : ∀ x : ℤ, x ∈ A2 → x ∈ Bu := by intro x hx; rw [hBu]; exact Finset.mem_union_left _ (Finset.mem_union_right _ hx) have htoBu_e : extra ∈ Bu := by rw [hBu]; exact Finset.mem_union_right _ (Finset.mem_singleton_self _) have htoBv_C1 : ∀ x : ℤ, x ∈ C1 → x ∈ Bv := by intro x hx; rw [hBv]; exact Finset.mem_union_left _ (Finset.mem_union_left _ hx) have htoBv_s : extra + (↑k:ℤ) ∈ Bv := by rw [hBv]; exact Finset.mem_union_left _ (Finset.mem_union_right _ (Finset.mem_singleton_self _)) have htoBv_C3 : ∀ x : ℤ, x ∈ C3 → x ∈ Bv := by intro x hx; rw [hBv]; exact Finset.mem_union_right _ hx
Neighbors of U and extra that fall outside S must lie in the candidate boundary sets Bu or Bv.
We prove five shift lemmas: 1. (hLemA) If i ∈ U and j = i + 1 ∉ U, writing i = r*k + j0 implies j0 + 1 cannot be less than m, so j0 + 1 = m and j = r*k + m ∈ A1 ⊆ Bu. 2. (hLemB) If i ∈ U and j = i - 1 ∉ U, writing i = r*k + j0 implies j0 cannot be positive (otherwise j0 - 1 < m gives j ∈ U using Nat.cast_sub), so j0 = 0 and j = r*k - 1 ∈ A2 ⊆ Bu. 3. (hLemC) If i ∈ U and j = i + k ∉ V, we cannot have r + 1 < R (which would put j ∈ U ⊆ V by Finset.mem_insert_of_mem), so r + 1 = R. Since j ≠ extra (by Finset.mem_insert_self), j0 < m - 1, so j ∈ C1 ⊆ Bv. 4. (hLemD) If i ∈ U and j = i - k ∉ V, we cannot have r ≥ 1 (which would put j ∈ U ⊆ V), so r = 0, giving j = j0 - k ∈ C3 ⊆ Bv. 5. (hExtraMinusK) Shifting extra down by k yields extra - k = (R-1)*k + (m-1), which belongs to U since R - 1 < R and m - 1 < m (Finset.mem_range).
uses
Finset.mem_range,Nat.cast_sub,Finset.mem_insert_of_mem,Finset.mem_insert_selfhave hLemA : ∀ i j : ℤ, i ∈ U → j = i + 1 → j ∉ U → j ∈ Bu := by intro i j hiU hji hjU obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : j0 + 1 < m · exfalso apply hjU rw [hUmem] refine ⟨r, by rw [Finset.mem_range]; exact hr, j0+1, by rw [Finset.mem_range]; exact hc, ?_⟩ rw [hji, hi_eq]; push_cast; ring · have hjm : j0 + 1 = m := by omega have hjeq : j = (↑(r*k+m) : ℤ) := by rw [hji, hi_eq]; push_cast; omega exact htoBu_A1 j (by rw [hA1]; exact Finset.mem_image.mpr ⟨r, by rw [Finset.mem_range]; exact hr, hjeq.symm⟩) have hLemB : ∀ i j : ℤ, i ∈ U → j = i - 1 → j ∉ U → j ∈ Bu := by intro i j hiU hji hjU obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : j0 = 0 · have hjeq : j = (↑(r*k) : ℤ) - 1 := by rw [hji, hi_eq, hc]; push_cast; ring exact htoBu_A2 j (by rw [hA2]; exact Finset.mem_image.mpr ⟨r, by rw [Finset.mem_range]; exact hr, hjeq.symm⟩) · have hj0pos : 1 ≤ j0 := by omega exfalso have hjU' : j ∈ U := by rw [hUmem] refine ⟨r, by rw [Finset.mem_range]; exact hr, j0-1, by rw [Finset.mem_range]; omega, ?_⟩ rw [hji, hi_eq] have hcast : ((j0 - 1 : ℕ) : ℤ) = (j0 : ℤ) - 1 := by rw [Nat.cast_sub hj0pos]; norm_num push_cast rw [hcast] ring exact hjU hjU' have hLemC : ∀ i j : ℤ, i ∈ U → j = i + ↑k → j ∉ V → j ∈ Bv := by intro i j hiU hji hjV obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : r + 1 < R · exfalso have hjU : j ∈ U := by rw [hUmem] refine ⟨r+1, by rw [Finset.mem_range]; exact hc, j0, by rw [Finset.mem_range]; exact hj0, ?_⟩ rw [hji, hi_eq]; push_cast; ring rw [hV] at hjV exact hjV (Finset.mem_insert_of_mem hjU) · have hrR : r + 1 = R := by omega have hjne : j ≠ extra := by rw [hV] at hjV intro h; rw [h] at hjV; exact hjV (Finset.mem_insert_self _ _) have hjeq : j = (↑R : ℤ) * ↑k + ↑j0 := by rw [hji, hi_eq, ← hrR]; push_cast; ring have hj0lt : j0 < m - 1 := by have hne : (j0 : ℤ) ≠ (m : ℤ) - 1 := by intro heq apply hjne rw [hjeq, hextra, heq]; ring have hj0z : (j0 : ℤ) < (m : ℤ) := by exact_mod_cast hj0 have hlt : (j0 : ℤ) < (m : ℤ) - 1 := by omega have : ((j0 + 1 : ℕ) : ℤ) < ((m : ℕ) : ℤ) := by push_cast; omega have hnat : j0 + 1 < m := by exact_mod_cast this omega exact htoBv_C1 j (by rw [hC1]; exact Finset.mem_image.mpr ⟨j0, by rw [Finset.mem_range]; exact hj0lt, hjeq.symm⟩) have hLemD : ∀ i j : ℤ, i ∈ U → j = i - ↑k → j ∉ V → j ∈ Bv := by intro i j hiU hji hjV obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : r = 0 · have hjeq : j = (↑j0 : ℤ) - ↑k := by rw [hji, hi_eq, hc]; push_cast; ring exact htoBv_C3 j (by rw [hC3]; exact Finset.mem_image.mpr ⟨j0, by rw [Finset.mem_range]; exact hj0, hjeq.symm⟩) · have hrpos : 1 ≤ r := by omega exfalso have hjU : j ∈ U := by rw [hUmem] refine ⟨r-1, by rw [Finset.mem_range]; omega, j0, by rw [Finset.mem_range]; exact hj0, ?_⟩ rw [hji, hi_eq] have hcast : ((r - 1 : ℕ) : ℤ) = (r : ℤ) - 1 := by rw [Nat.cast_sub hrpos]; norm_num push_cast rw [hcast] ring rw [hV] at hjV exact hjV (Finset.mem_insert_of_mem hjU) have hExtraMinusK : extra - (↑k : ℤ) ∈ U := by rw [hUmem] refine ⟨R-1, by rw [Finset.mem_range]; omega, m-1, by rw [Finset.mem_range]; omega, ?_⟩ rw [hextra] have hRsub : ((R-1:ℕ):ℤ) = (R:ℤ) - 1 := by rw [Nat.cast_sub hR1]; norm_num have hMsub : ((m-1:ℕ):ℤ) = (m:ℤ) - 1 := by rw [Nat.cast_sub hm1]; norm_num push_cast rw [hRsub, hMsub] ring
The external boundary of S is contained in B (petersen_strip_boundary k S ⊆ B).
For any w ∈ ∂S, by mem_petersen_strip_boundary, w ∉ S and w is adjacent to some u0 ∈ S in petersen_strip k. We analyze cases on u0 and w: - u0 = u(i) with i ∈ U: if w = u(j), then j = i ± 1 ∉ U, so j ∈ Bu by hLemA or hLemB; if w = v(j), then j = i ∈ U ⊆ V, meaning w ∈ S, a contradiction. - u0 = v(i) with i ∈ V = U ∪ {extra}: if w = u(j), then j = i ∉ U, so i must be extra, whence j = extra ∈ Bu; if w = v(j), then j = i ± k ∉ V. When i = extra, j = extra + k ∈ Bv (since extra - k ∈ U ⊆ V by Finset.mem_insert_of_mem, which would contradict w ∉ S). When i ∈ U, hLemC or hLemD shows j ∈ Bv. In all valid cases, w ∈ B.
uses
mem_petersen_strip_boundary,petersen_strip,Finset.mem_insert_of_memhave hsub : petersen_strip_boundary k S ⊆ B := by intro w hw have hwb := (mem_petersen_strip_boundary k S w).mp hw obtain ⟨hwS, u0, hu0, hadj⟩ := hwb cases u0 with | u i => have hiU : i ∈ U := (huS i).mp hu0 cases w with | u j => have hcase : j = i + 1 ∨ j = i - 1 := by simpa only [petersen_strip] using hadj have hjU : j ∉ U := fun h => hwS ((huS j).mpr h) rcases hcase with h | h · exact hmemB_u j (hLemA i j hiU h hjU) · exact hmemB_u j (hLemB i j hiU h hjU) | v j => have hcase : j = i := by simpa only [petersen_strip] using hadj exfalso apply hwS rw [hcase] exact (hvS i).mpr (by rw [hV]; exact Finset.mem_insert_of_mem hiU) | v i => have hiV : i ∈ V := (hvS i).mp hu0 cases w with | u j => have hcase : j = i := by simpa only [petersen_strip] using hadj have hjU : j ∉ U := fun h => hwS ((huS j).mpr h) have hi : i = extra ∨ i ∈ U := by rw [hV] at hiV; simpa using hiV rcases hi with h | h · exact hmemB_u j (by rw [hcase, h]; exact htoBu_e) · exact absurd (by rw [hcase]; exact h) hjU | v j => have hcase : k ≠ 0 ∧ (j = i + ↑k ∨ j = i - ↑k) := by simpa only [petersen_strip] using hadj have hjV : j ∉ V := fun h => hwS ((hvS j).mpr h) obtain ⟨_, hcases⟩ := hcase have hi : i = extra ∨ i ∈ U := by rw [hV] at hiV; simpa using hiV rcases hi with hie | hiU · rcases hcases with hjc | hjc · exact hmemB_v j (by rw [hjc, hie]; exact htoBv_s) · exfalso apply hjV rw [hjc, hie, hV] exact Finset.mem_insert_of_mem hExtraMinusK · rcases hcases with hjc | hjc · exact hmemB_v j (hLemC i j hiU hjc hjV) · exact hmemB_v j (hLemD i j hiU hjc hjV)
The candidate boundary B has cardinality at most 2k + 1.
By Finset.card_image_le, le_of_eq, and Finset.card_range, the component finsets have sizes |A1| ≤ R, |A2| ≤ R, |C1| ≤ m - 1, and |C3| ≤ m. Applying the union bound Finset.card_union_le and Finset.card_singleton gives |Bu| ≤ |A1| + |A2| + 1 ≤ 2*R + 1, and |Bv| ≤ |C1| + 1 + |C3| ≤ 2*m. Since R + m = k, their sum is |B| ≤ |Bu| + |Bv| ≤ 2*R + 1 + 2*m = 2*(R + m) + 1 = 2*k + 1.
uses
Finset.card_image_le,le_of_eq,Finset.card_range,Finset.card_union_le,Finset.card_singletonhave hA1card : A1.card ≤ R := by rw [hA1] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range R)) have hA2card : A2.card ≤ R := by rw [hA2] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range R)) have hC1card : C1.card ≤ m - 1 := by rw [hC1] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range (m-1))) have hC3card : C3.card ≤ m := by rw [hC3] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range m)) have hBucard : Bu.card ≤ 2*R+1 := by rw [hBu] have h1 := Finset.card_union_le (A1 ∪ A2) ({(extra:ℤ)}) have h2 := Finset.card_union_le A1 A2 simp only [Finset.card_singleton] at h1 omega have hBvcard : Bv.card ≤ 2*m := by rw [hBv] have h1 := Finset.card_union_le (C1 ∪ {(extra + (↑k:ℤ))}) C3 have h2 := Finset.card_union_le C1 ({(extra + (↑k:ℤ))}) simp only [Finset.card_singleton] at h2 omega have hBcard : B.card ≤ 2*k+1 := by rw [hB] have h1 := Finset.card_union_le (Finset.image PetersenStripVertex.u Bu) (Finset.image PetersenStripVertex.v Bv) have h2 : (Finset.image PetersenStripVertex.u Bu).card ≤ Bu.card := Finset.card_image_le have h3 : (Finset.image PetersenStripVertex.v Bv).card ≤ Bv.card := Finset.card_image_le omega
The external boundary of the witness set has cardinality at most 2k + 1.
Since the boundary is a subset of B, Finset.card_le_card implies that its cardinality is bounded by |B|, which is at most 2k + 1.
uses
Finset.card_le_cardcalc (petersen_strip_boundary k S).card ≤ B.card := Finset.card_le_card hsub _ ≤ 2*k+1 := hBcard
Finset.card_image_le- The cardinality of the image f(s) is at most the cardinality of s.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_range- The range of natural numbers less than n has cardinality n.
Finset.card_singleton- The cardinality of a singleton set is 1.
Finset.card_union_le- The cardinality of the union s ∪ t is at most |s| + |t|.
Finset.mem_biUnion- An element belongs to the union of a family of finsets if and only if it belongs to at least one finset in the family.
Finset.mem_image- An element b belongs to the image f(s) if and only if there is some a ∈ s with f(a) = b.
Finset.mem_insert_of_mem- An element belongs to insert b s if it already belongs to s.
Finset.mem_insert_self- An element belongs to the set obtained by inserting it into any set.
Finset.mem_range- A natural number m belongs to range n if and only if m < n.
Finset.mem_singleton_self- An element belongs to its own singleton set.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_union_left- If a ∈ s, then a belongs to s ∪ t.
Finset.mem_union_right- If a ∈ t, then a belongs to s ∪ t.
le_of_eq- If a = b, then a ≤ b.
Nat.cast_sub- For m ≤ n, the integer cast of n - m equals the difference of the integer casts of n and m.
Nat.mod_two_eq_zero_or_one- Every natural number modulo 2 is equal to 0 or 1.
if_neg- If a condition is false, an if-then-else on that condition evaluates to the else branch.
if_pos- If a condition is true, an if-then-else on that condition evaluates to the then branch.
mem_petersen_strip_boundary- A vertex w is in the external boundary of S in the generalized Petersen strip if and only if w ∉ S and w is adjacent to some vertex in S.
petersen_strip- The definition of the generalized Petersen strip graph on vertex set PetersenStripVertex with jump parameter k.
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.
/-- The external boundary of the witness set in the generalized Petersen strip has cardinality at most 2k + 1 for all k ≥ 8. -/theorem petersen_strip_witness_boundary_card (k : ℕ) (hk : 8 ≤ k) : (petersen_strip_boundary k (petersen_strip_witness k)).card ≤ 2 * k + 1 := by set m : ℕ := k / 2 with hm set R : ℕ := (if (k % 2 == 0) = true then m else m + 1) with hR set U : Finset ℤ := (Finset.range R).biUnion (fun r => Finset.image (fun j => (↑(r*k+j) : ℤ)) (Finset.range m)) with hU set extra : ℤ := (↑R : ℤ) * ↑k + ↑m - 1 with hextra set V : Finset ℤ := insert extra U with hV set S : Finset PetersenStripVertex := Finset.image PetersenStripVertex.u U ∪ Finset.image PetersenStripVertex.v V with hSdef have hS : petersen_strip_witness k = S := by rw [hSdef] unfold petersen_strip_witness simp only [← hm, ← hR, ← hU, ← hextra, ← hV] rw [hS] have hm4 : 4 ≤ m := by rw [hm]; omega have hm1 : 1 ≤ m := by omega have hR1 : 1 ≤ R := by rw [hR]; split_ifs <;> omega have hRk : R + m = k := by have h2 : k % 2 = 0 ∨ k % 2 = 1 := Nat.mod_two_eq_zero_or_one k rw [hR, hm] rcases h2 with h2 | h2 · have hb : (k % 2 == 0) = true := by simpa using h2 rw [if_pos hb]; omega · have hb : ¬ ((k % 2 == 0) = true) := by simp [h2] rw [if_neg hb]; omega set A1 : Finset ℤ := Finset.image (fun r => (↑(r*k+m) : ℤ)) (Finset.range R) with hA1 set A2 : Finset ℤ := Finset.image (fun r => (↑(r*k) : ℤ) - 1) (Finset.range R) with hA2 set C1 : Finset ℤ := Finset.image (fun j => (↑R : ℤ) * ↑k + ↑j) (Finset.range (m-1)) with hC1 set C3 : Finset ℤ := Finset.image (fun (j : ℕ) => (↑j : ℤ) - ↑k) (Finset.range m) with hC3 set Bu : Finset ℤ := A1 ∪ A2 ∪ {extra} with hBu set Bv : Finset ℤ := C1 ∪ {extra + ↑k} ∪ C3 with hBv set B : Finset PetersenStripVertex := Finset.image PetersenStripVertex.u Bu ∪ Finset.image PetersenStripVertex.v Bv with hB have hUmem : ∀ i : ℤ, i ∈ U ↔ ∃ r ∈ Finset.range R, ∃ j ∈ Finset.range m, i = (↑(r*k+j) : ℤ) := by intro i rw [hU] simp only [Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨r, hr, j, hj, hji⟩; exact ⟨r, hr, j, hj, hji.symm⟩ · rintro ⟨r, hr, j, hj, hij⟩; exact ⟨r, hr, j, hj, hij.symm⟩ have huS : ∀ i, (PetersenStripVertex.u i ∈ S) ↔ i ∈ U := by intro i; rw [hSdef] simp only [Finset.mem_union, Finset.mem_image] constructor · rintro (⟨i', hi', he⟩ | ⟨i', hi', he⟩) · cases he; exact hi' · exact absurd he (by simp) · intro hi; exact Or.inl ⟨i, hi, rfl⟩ have hvS : ∀ i, (PetersenStripVertex.v i ∈ S) ↔ i ∈ V := by intro i; rw [hSdef] simp only [Finset.mem_union, Finset.mem_image] constructor · rintro (⟨i', hi', he⟩ | ⟨i', hi', he⟩) · exact absurd he (by simp) · cases he; exact hi' · intro hi; exact Or.inr ⟨i, hi, rfl⟩ have hmemB_u : ∀ j : ℤ, j ∈ Bu → PetersenStripVertex.u j ∈ B := by intro j hj; rw [hB]; exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨j, hj, rfl⟩) have hmemB_v : ∀ j : ℤ, j ∈ Bv → PetersenStripVertex.v j ∈ B := by intro j hj; rw [hB]; exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨j, hj, rfl⟩) have htoBu_A1 : ∀ x : ℤ, x ∈ A1 → x ∈ Bu := by intro x hx; rw [hBu]; exact Finset.mem_union_left _ (Finset.mem_union_left _ hx) have htoBu_A2 : ∀ x : ℤ, x ∈ A2 → x ∈ Bu := by intro x hx; rw [hBu]; exact Finset.mem_union_left _ (Finset.mem_union_right _ hx) have htoBu_e : extra ∈ Bu := by rw [hBu]; exact Finset.mem_union_right _ (Finset.mem_singleton_self _) have htoBv_C1 : ∀ x : ℤ, x ∈ C1 → x ∈ Bv := by intro x hx; rw [hBv]; exact Finset.mem_union_left _ (Finset.mem_union_left _ hx) have htoBv_s : extra + (↑k:ℤ) ∈ Bv := by rw [hBv]; exact Finset.mem_union_left _ (Finset.mem_union_right _ (Finset.mem_singleton_self _)) have htoBv_C3 : ∀ x : ℤ, x ∈ C3 → x ∈ Bv := by intro x hx; rw [hBv]; exact Finset.mem_union_right _ hx have hLemA : ∀ i j : ℤ, i ∈ U → j = i + 1 → j ∉ U → j ∈ Bu := by intro i j hiU hji hjU obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : j0 + 1 < m · exfalso apply hjU rw [hUmem] refine ⟨r, by rw [Finset.mem_range]; exact hr, j0+1, by rw [Finset.mem_range]; exact hc, ?_⟩ rw [hji, hi_eq]; push_cast; ring · have hjm : j0 + 1 = m := by omega have hjeq : j = (↑(r*k+m) : ℤ) := by rw [hji, hi_eq]; push_cast; omega exact htoBu_A1 j (by rw [hA1]; exact Finset.mem_image.mpr ⟨r, by rw [Finset.mem_range]; exact hr, hjeq.symm⟩) have hLemB : ∀ i j : ℤ, i ∈ U → j = i - 1 → j ∉ U → j ∈ Bu := by intro i j hiU hji hjU obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : j0 = 0 · have hjeq : j = (↑(r*k) : ℤ) - 1 := by rw [hji, hi_eq, hc]; push_cast; ring exact htoBu_A2 j (by rw [hA2]; exact Finset.mem_image.mpr ⟨r, by rw [Finset.mem_range]; exact hr, hjeq.symm⟩) · have hj0pos : 1 ≤ j0 := by omega exfalso have hjU' : j ∈ U := by rw [hUmem] refine ⟨r, by rw [Finset.mem_range]; exact hr, j0-1, by rw [Finset.mem_range]; omega, ?_⟩ rw [hji, hi_eq] have hcast : ((j0 - 1 : ℕ) : ℤ) = (j0 : ℤ) - 1 := by rw [Nat.cast_sub hj0pos]; norm_num push_cast rw [hcast] ring exact hjU hjU' have hLemC : ∀ i j : ℤ, i ∈ U → j = i + ↑k → j ∉ V → j ∈ Bv := by intro i j hiU hji hjV obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : r + 1 < R · exfalso have hjU : j ∈ U := by rw [hUmem] refine ⟨r+1, by rw [Finset.mem_range]; exact hc, j0, by rw [Finset.mem_range]; exact hj0, ?_⟩ rw [hji, hi_eq]; push_cast; ring rw [hV] at hjV exact hjV (Finset.mem_insert_of_mem hjU) · have hrR : r + 1 = R := by omega have hjne : j ≠ extra := by rw [hV] at hjV intro h; rw [h] at hjV; exact hjV (Finset.mem_insert_self _ _) have hjeq : j = (↑R : ℤ) * ↑k + ↑j0 := by rw [hji, hi_eq, ← hrR]; push_cast; ring have hj0lt : j0 < m - 1 := by have hne : (j0 : ℤ) ≠ (m : ℤ) - 1 := by intro heq apply hjne rw [hjeq, hextra, heq]; ring have hj0z : (j0 : ℤ) < (m : ℤ) := by exact_mod_cast hj0 have hlt : (j0 : ℤ) < (m : ℤ) - 1 := by omega have : ((j0 + 1 : ℕ) : ℤ) < ((m : ℕ) : ℤ) := by push_cast; omega have hnat : j0 + 1 < m := by exact_mod_cast this omega exact htoBv_C1 j (by rw [hC1]; exact Finset.mem_image.mpr ⟨j0, by rw [Finset.mem_range]; exact hj0lt, hjeq.symm⟩) have hLemD : ∀ i j : ℤ, i ∈ U → j = i - ↑k → j ∉ V → j ∈ Bv := by intro i j hiU hji hjV obtain ⟨r, hr, j0, hj0, hi_eq⟩ := (hUmem i).mp hiU rw [Finset.mem_range] at hr hj0 by_cases hc : r = 0 · have hjeq : j = (↑j0 : ℤ) - ↑k := by rw [hji, hi_eq, hc]; push_cast; ring exact htoBv_C3 j (by rw [hC3]; exact Finset.mem_image.mpr ⟨j0, by rw [Finset.mem_range]; exact hj0, hjeq.symm⟩) · have hrpos : 1 ≤ r := by omega exfalso have hjU : j ∈ U := by rw [hUmem] refine ⟨r-1, by rw [Finset.mem_range]; omega, j0, by rw [Finset.mem_range]; exact hj0, ?_⟩ rw [hji, hi_eq] have hcast : ((r - 1 : ℕ) : ℤ) = (r : ℤ) - 1 := by rw [Nat.cast_sub hrpos]; norm_num push_cast rw [hcast] ring rw [hV] at hjV exact hjV (Finset.mem_insert_of_mem hjU) have hExtraMinusK : extra - (↑k : ℤ) ∈ U := by rw [hUmem] refine ⟨R-1, by rw [Finset.mem_range]; omega, m-1, by rw [Finset.mem_range]; omega, ?_⟩ rw [hextra] have hRsub : ((R-1:ℕ):ℤ) = (R:ℤ) - 1 := by rw [Nat.cast_sub hR1]; norm_num have hMsub : ((m-1:ℕ):ℤ) = (m:ℤ) - 1 := by rw [Nat.cast_sub hm1]; norm_num push_cast rw [hRsub, hMsub] ring have hsub : petersen_strip_boundary k S ⊆ B := by intro w hw have hwb := (mem_petersen_strip_boundary k S w).mp hw obtain ⟨hwS, u0, hu0, hadj⟩ := hwb cases u0 with | u i => have hiU : i ∈ U := (huS i).mp hu0 cases w with | u j => have hcase : j = i + 1 ∨ j = i - 1 := by simpa only [petersen_strip] using hadj have hjU : j ∉ U := fun h => hwS ((huS j).mpr h) rcases hcase with h | h · exact hmemB_u j (hLemA i j hiU h hjU) · exact hmemB_u j (hLemB i j hiU h hjU) | v j => have hcase : j = i := by simpa only [petersen_strip] using hadj exfalso apply hwS rw [hcase] exact (hvS i).mpr (by rw [hV]; exact Finset.mem_insert_of_mem hiU) | v i => have hiV : i ∈ V := (hvS i).mp hu0 cases w with | u j => have hcase : j = i := by simpa only [petersen_strip] using hadj have hjU : j ∉ U := fun h => hwS ((huS j).mpr h) have hi : i = extra ∨ i ∈ U := by rw [hV] at hiV; simpa using hiV rcases hi with h | h · exact hmemB_u j (by rw [hcase, h]; exact htoBu_e) · exact absurd (by rw [hcase]; exact h) hjU | v j => have hcase : k ≠ 0 ∧ (j = i + ↑k ∨ j = i - ↑k) := by simpa only [petersen_strip] using hadj have hjV : j ∉ V := fun h => hwS ((hvS j).mpr h) obtain ⟨_, hcases⟩ := hcase have hi : i = extra ∨ i ∈ U := by rw [hV] at hiV; simpa using hiV rcases hi with hie | hiU · rcases hcases with hjc | hjc · exact hmemB_v j (by rw [hjc, hie]; exact htoBv_s) · exfalso apply hjV rw [hjc, hie, hV] exact Finset.mem_insert_of_mem hExtraMinusK · rcases hcases with hjc | hjc · exact hmemB_v j (hLemC i j hiU hjc hjV) · exact hmemB_v j (hLemD i j hiU hjc hjV) have hA1card : A1.card ≤ R := by rw [hA1] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range R)) have hA2card : A2.card ≤ R := by rw [hA2] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range R)) have hC1card : C1.card ≤ m - 1 := by rw [hC1] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range (m-1))) have hC3card : C3.card ≤ m := by rw [hC3] exact Finset.card_image_le.trans (le_of_eq (Finset.card_range m)) have hBucard : Bu.card ≤ 2*R+1 := by rw [hBu] have h1 := Finset.card_union_le (A1 ∪ A2) ({(extra:ℤ)}) have h2 := Finset.card_union_le A1 A2 simp only [Finset.card_singleton] at h1 omega have hBvcard : Bv.card ≤ 2*m := by rw [hBv] have h1 := Finset.card_union_le (C1 ∪ {(extra + (↑k:ℤ))}) C3 have h2 := Finset.card_union_le C1 ({(extra + (↑k:ℤ))}) simp only [Finset.card_singleton] at h2 omega have hBcard : B.card ≤ 2*k+1 := by rw [hB] have h1 := Finset.card_union_le (Finset.image PetersenStripVertex.u Bu) (Finset.image PetersenStripVertex.v Bv) have h2 : (Finset.image PetersenStripVertex.u Bu).card ≤ Bu.card := Finset.card_image_le have h3 : (Finset.image PetersenStripVertex.v Bv).card ≤ Bv.card := Finset.card_image_le omega calc (petersen_strip_boundary k S).card ≤ B.card := Finset.card_le_card hsub _ ≤ 2*k+1 := hBcard