AFTD Auto-Formalizing Theoretical Domains

petersen_strip_witness_boundary_card

theoremverified

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 S is 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 k is the infinite simple graph with vertex set PetersenStripVertex where vertices u i and…
Used by 1

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.

  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.

    lines 3–13

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

    lines 14–24

    uses Nat.mod_two_eq_zero_or_one, if_pos, if_neg

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

    lines 25–31

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

    lines 32–69

    uses Finset.mem_biUnion, Finset.mem_image, Finset.mem_union, Finset.mem_union_left, Finset.mem_union_right, Finset.mem_singleton_self

      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
  5. 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).

    lines 70–160

    uses Finset.mem_range, Nat.cast_sub, Finset.mem_insert_of_mem, Finset.mem_insert_self

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

    lines 161–205

    uses mem_petersen_strip_boundary, petersen_strip, Finset.mem_insert_of_mem

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

    lines 206–235

    uses Finset.card_image_le, le_of_eq, Finset.card_range, Finset.card_union_le, Finset.card_singleton

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

    lines 236–237

    uses Finset.card_le_card

      calc (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

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