AFTD Auto-Formalizing Theoretical Domains

connected_independence_local_clique_card_bound

theoremverified

Let r and s be integers at least three and let d be an integer with 3r+3s<d+10. A connected finite simple graph with independence number at most s, maximum degree at most d, and every edge in an r-vertex clique has at most sd−r+2 vertices.

Statement

theorem connected_independence_local_clique_card_bound
    (r s d : ℕ) (hr : 3 ≤ r) (hs : 3 ≤ s) (hgap : 3 * r + 3 * s < d + 10)
    (α : Type) [Fintype α] [DecidableEq α]
    (G : SimpleGraph α) [DecidableRel G.Adj]
    (hconn : G.Connected) (hindep : G.IndepSetFree (s + 1))
    (hdeg : ∀ v, G.degree v ≤ d)
    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,
      S.card = r ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :
    Fintype.card α ≤ s * d - r + 2
Source
General auxiliary-graph route for directed cycle packing, using Mathlib SimpleGraph.colorable_of_cliqueFree_lt_minDegree; experiment 12548 checks sharp examples.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

Assume for contradiction that the graph has at least sd - r + 3 vertices. Under the maximum degree bound and the gap condition 3r + 3s < d + 10, the complement graph Gᶜ has no (s + 1)-clique and high minimum degree, so an Andrásfai-Erdős-Sós type theorem guarantees that Gᶜ is s-colorable, partitioning V(G) into s cliques of size at most d. An r-clique containing a cross-edge between two different color classes restricts the sum of those two clique sizes to at most 2d + 2 - r, which bounds the total number of vertices by (s - 2)d + 2d + 2 - r = sd - r + 2, a contradiction.

  1. The arithmetic inequality (3 * s - 4) * n / (3 * s - 1) < n - 1 - d holds under the parameter hypotheses.

    By substituting s = a + 3 and n = e + 1 + d to eliminate boundary offsets, clearing the division denominator with Nat.div_lt_iff_lt_mul, non-linear arithmetic verifies that 3 * r + 3 * s < d + 10 and s * d + 3 ≤ n + r imply the inequality.

    lines 4–10

    uses Nat.div_lt_iff_lt_mul

      obtain ⟨a, rfl⟩ : ∃ a, s = a + 3 := ⟨s - 3, by omega⟩
      obtain ⟨e, rfl⟩ : ∃ e, n = e + 1 + d := ⟨n - 1 - d, by omega⟩
      have h1 : 3 * (a + 3) - 4 = 3 * a + 5 := by omega
      have h2 : 3 * (a + 3) - 1 = 3 * a + 8 := by omega
      have h3 : e + 1 + d - 1 - d = e := by omega
      rw [h1, h2, h3, Nat.div_lt_iff_lt_mul (by omega)]
      nlinarith
  2. Assume for contradiction that |V(G)| > sd - r + 2; then sd + 3 ≤ |V(G)| + r and d + 1 < |V(G)|.

    We proceed by contradiction and assume |V(G)| > sd - r + 2. Since s ≥ 3 and 3r + 3s < d + 10, integer arithmetic establishes that s * d + 3 ≤ |V(G)| + r and d + 1 < |V(G)|.

    lines 21–26

    uses Nat.mul_le_mul_right

      classical
      letI : Nonempty α := hconn.nonempty
      by_contra hn
      have h3d : 3 * d ≤ s * d := Nat.mul_le_mul_right d hs
      have hn' : s * d + 3 ≤ Fintype.card α + r := by omega
      have hnd : d + 1 < Fintype.card α := by omega
  3. The complement graph Gᶜ has no (s + 1)-clique, satisfies δ(Gᶜ) > (3s - 4)|V(G)| / (3s - 1), and is therefore s-colorable.

    Each vertex in Gᶜ has degree |V(G)| - 1 - deg_G(v) ≥ |V(G)| - 1 - d, so δ(Gᶜ) ≥ |V(G)| - 1 - d. Combined with the arithmetic lemma cicb_dense, this gives δ(Gᶜ) > (3s - 4)|V(G)| / (3s - 1). Since G has independence number at most s, Gᶜ is (s + 1)-clique-free. By SimpleGraph.colorable_of_cliqueFree_lt_minDegree, Gᶜ admits an s-coloring col.

    lines 27–38

    uses cicb_dense, lt_of_lt_of_le, SimpleGraph.colorable_of_cliqueFree_lt_minDegree

      have hmin : Fintype.card α - 1 - d ≤ Gᶜ.minDegree := by
        apply Gᶜ.le_minDegree_of_forall_le_degree
        intro v
        rw [G.degree_compl]
        have hd := hdeg v
        omega
      have hf : Gᶜ.CliqueFree (s + 1) := by simpa using hindep
      have hdense : (3 * s - 4) * Fintype.card α / (3 * s - 1) < Gᶜ.minDegree :=
        lt_of_lt_of_le (cicb_dense s d r _ hs hgap hn' hnd) hmin
      have hcolor : Gᶜ.Colorable s :=
        SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := s) hf hdense
      obtain ⟨col⟩ := hcolor
  4. The color classes P i partition V(G) into s cliques of G.

    The fibers P i of the coloring col partition V(G), so the sum of their cardinalities is |V(G)| by Finset.card_eq_sum_card_fiberwise. Any two distinct vertices in the same part P i cannot be adjacent in Gᶜ because they have the same color; hence, they are adjacent in G, so each P i induces a clique in G.

    lines 39–52

    uses Finset.card_eq_sum_card_fiberwise

      let P : Fin s → Finset α := fun i => Finset.univ.filter fun x => col x = i
      have hmem : ∀ i x, x ∈ P i ↔ col x = i := by intro i x; simp [P]
      have hinside : ∀ (i : Fin s) (x : α), x ∈ P i → ∀ y ∈ P i, x ≠ y → G.Adj x y := by
        intro i x hx y hy hxy
        have hxe := (hmem i x).mp hx
        have hye := (hmem i y).mp hy
        by_contra h
        have hcomp : Gᶜ.Adj x y := ⟨hxy, h⟩
        have hncol := col.valid hcomp
        exact hncol (hxe.trans hye.symm)
      have hsum : ∑ i, (P i).card = Fintype.card α := by
        have h := Finset.card_eq_sum_card_fiberwise
          (f := fun x : α => col x) (s := Finset.univ) (t := Finset.univ) (by simp)
        simpa [P] using h.symm
  5. Each color class P i has size at most d.

    For any vertex x in P i, every other vertex of P i is a neighbor of x in G, so |P i| - 1 ≤ deg_G(x) ≤ d, showing |P i| ≤ d + 1. If equality |P i| = d + 1 held, P i \ {u} would equal the entire neighborhood N_G(u) for every u in P i, making P i closed under adjacency. Since G is connected, this would imply P i = V(G), so |V(G)| = d + 1, contradicting |V(G)| > d + 1. Hence, |P i| ≤ d for all i.

    lines 53–103

    uses SimpleGraph.mem_neighborFinset, SimpleGraph.card_neighborFinset_eq_degree

      have hpartcap : ∀ i, (P i).card ≤ d + 1 := by
        intro i
        by_cases hne : (P i).Nonempty
        · obtain ⟨x, hx⟩ := hne
          have hsub : (P i).erase x ⊆ G.neighborFinset x := by
            intro y hy
            have hy' := Finset.mem_erase.mp hy
            exact (SimpleGraph.mem_neighborFinset G x y).mpr
              (hinside i x hx y hy'.2 hy'.1.symm)
          have hc := Finset.card_le_card hsub
          have he := Finset.card_erase_add_one hx
          rw [SimpleGraph.card_neighborFinset_eq_degree] at hc
          have hd := hdeg x
          omega
        · have he : P i = ∅ := Finset.not_nonempty_iff_eq_empty.mp hne
          simp [he]
      have hpartsmall : ∀ i, (P i).card ≤ d := by
        intro i
        by_contra h
        have hs' : (P i).card = d + 1 := by have := hpartcap i; omega
        have hne : (P i).Nonempty := Finset.card_pos.mp (by omega)
        obtain ⟨x, hx⟩ := hne
        have hclosed : ∀ u ∈ P i, ∀ v, G.Adj u v → v ∈ P i := by
          intro u hu v huv
          have hsub : (P i).erase u ⊆ G.neighborFinset u := by
            intro z hz
            have hz' := Finset.mem_erase.mp hz
            exact (SimpleGraph.mem_neighborFinset G u z).mpr
              (hinside i u hu z hz'.2 hz'.1.symm)
          have he := Finset.card_erase_add_one hu
          have hcard : (G.neighborFinset u).card ≤ ((P i).erase u).card := by
            rw [SimpleGraph.card_neighborFinset_eq_degree]
            have hd := hdeg u
            omega
          have heq := Finset.eq_of_subset_of_card_le hsub hcard
          have hv : v ∈ G.neighborFinset u := (SimpleGraph.mem_neighborFinset G u v).mpr huv
          rw [← heq] at hv
          exact (Finset.mem_erase.mp hv).2
        have hwalk : ∀ {u v}, G.Walk u v → u ∈ P i → v ∈ P i := by
          intro u v p
          induction p with
          | nil => intro hu; exact hu
          | cons h p ih => intro hu; exact ih (hclosed _ hu _ h)
        have hall : P i = Finset.univ := by
          apply Finset.eq_univ_iff_forall.mpr
          intro v
          obtain ⟨p⟩ := hconn x v
          exact hwalk p hx
        rw [hall] at hs'
        simp at hs'
        omega
  6. There exists an edge xy between two distinct color classes, and an r-clique Q containing both x and y.

    If every edge had both endpoints in the same color class, connectedness of G would force all vertices into a single color class, giving |V(G)| ≤ d < |V(G)|, a contradiction. Thus there exists an edge xy with col(x) ≠ col(y). By hypothesis, xy is contained in an r-vertex clique Q in G.

    lines 104–122

    uses Finset.card_univ

      have hcross : ∃ x y, G.Adj x y ∧ col x ≠ col y := by
        by_contra h
        push_neg at h
        have hwalk : ∀ {u v}, G.Walk u v → col u = col v := by
          intro u v p
          induction p with
          | nil => rfl
          | cons hab p ih => exact (h _ _ hab).trans ih
        obtain ⟨x⟩ := (inferInstance : Nonempty α)
        have hall : P (col x) = Finset.univ := by
          apply Finset.eq_univ_iff_forall.mpr
          intro v
          obtain ⟨p⟩ := hconn x v
          exact (hmem _ v).mpr (hwalk p).symm
        have := hpartsmall (col x)
        rw [hall, Finset.card_univ] at this
        omega
      obtain ⟨x, y, hxy, hnecol⟩ := hcross
      obtain ⟨Q, hQcard, hxQ, hyQ, hQcl⟩ := hclique x y hxy
  7. For any part P i and any vertex u ∈ P i ∩ Q, |P i| + r ≤ d + 1 + |Q ∩ P i|.

    For u ∈ P i ∩ Q, the sets P i \ {u} and Q \ P i are disjoint subsets of the neighborhood N_G(u), since both P i and Q are cliques in G. The sum of their cardinalities is (|P i| - 1) + (|Q| - |Q ∩ P i|) ≤ deg_G(u) ≤ d. Since |Q| = r, rearranging yields |P i| + r ≤ d + 1 + |Q ∩ P i|.

    lines 123–150

    uses SimpleGraph.mem_neighborFinset, SimpleGraph.card_neighborFinset_eq_degree, Finset.card_union_of_disjoint, Finset.card_sdiff_add_card_inter

      have hQbound : ∀ i u, u ∈ P i → u ∈ Q →
          (P i).card + r ≤ d + 1 + (Q ∩ P i).card := by
        intro i u huP huQ
        let E := (P i).erase u
        let R := Q \ P i
        have hdis : Disjoint E R := by
          apply Finset.disjoint_left.mpr
          intro z hzE hzR
          have hzP := (Finset.mem_erase.mp hzE).2
          have hznot := (Finset.mem_sdiff.mp hzR).2
          exact hznot hzP
        have hsub : E ∪ R ⊆ G.neighborFinset u := by
          intro z hz
          rcases Finset.mem_union.mp hz with hzE | hzR
          · have hz' := Finset.mem_erase.mp hzE
            exact (SimpleGraph.mem_neighborFinset G u z).mpr
              (hinside i u huP z hz'.2 hz'.1.symm)
          · have hz' := Finset.mem_sdiff.mp hzR
            have hne : u ≠ z := by intro he; subst z; exact hz'.2 huP
            exact (SimpleGraph.mem_neighborFinset G u z).mpr (hQcl huQ hz'.1 hne)
        have hcard := Finset.card_le_card hsub
        rw [SimpleGraph.card_neighborFinset_eq_degree, Finset.card_union_of_disjoint hdis] at hcard
        have he := Finset.card_erase_add_one huP
        have hr' := Finset.card_sdiff_add_card_inter Q (P i)
        have hd := hdeg u
        change ((P i).erase u).card + R.card ≤ G.degree u at hcard
        change R.card + (Q ∩ P i).card = Q.card at hr'
        omega
  8. The two parts containing x and y satisfy |P(col x)| + |P(col y)| + r ≤ 2d + 2.

    Applying the bound from the previous step to x ∈ P(col x) ∩ Q and y ∈ P(col y) ∩ Q gives bounds on |P(col x)| + r and |P(col y)| + r. Because col(x) ≠ col(y), the intersections Q ∩ P(col x) and Q ∩ P(col y) are disjoint subsets of Q, so their cardinalities sum to at most |Q| = r. Adding the two bounds gives |P(col x)| + |P(col y)| + 2r ≤ 2d + 2 + r.

    lines 151–165

    uses Finset.card_union_of_disjoint

      have hxi : x ∈ P (col x) := (hmem (col x) x).2 rfl
      have hyj : y ∈ P (col y) := (hmem (col y) y).2 rfl
      have hxbound := hQbound (col x) x hxi hxQ
      have hybound := hQbound (col y) y hyj hyQ
      have hdis : Disjoint (Q ∩ P (col x)) (Q ∩ P (col y)) := by
        apply Finset.disjoint_left.mpr
        intro z hz1 hz2
        have h1 := (hmem (col x) z).mp (Finset.mem_inter.mp hz1).2
        have h2 := (hmem (col y) z).mp (Finset.mem_inter.mp hz2).2
        exact hnecol (h1.symm.trans h2)
      have hsub : (Q ∩ P (col x)) ∪ (Q ∩ P (col y)) ⊆ Q := by
        intro z hz
        rcases Finset.mem_union.mp hz with h | h <;> exact (Finset.mem_inter.mp h).1
      have hc := Finset.card_le_card hsub
      rw [Finset.card_union_of_disjoint hdis, hQcard] at hc
  9. The remaining s - 2 color classes have total cardinality at most (s - 2) * d.

    There are s - 2 color classes other than P(col x) and P(col y). Since each color class has cardinality at most d, their sum is bounded by (s - 2) * d using Finset.sum_le_sum and Finset.sum_const.

    lines 167–175

    uses Finset.sum_le_sum, Finset.sum_const, smul_eq_mul

      have hrest : ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card ≤ (s - 2) * d := by
        have hcardrest : ((Finset.univ.erase (col x)).erase (col y)).card = s - 2 := by
          rw [Finset.card_erase_of_mem (Finset.mem_erase.mpr ⟨hnecol.symm, Finset.mem_univ _⟩),
            Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]
          omega
        calc ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card
            ≤ ∑ _i ∈ (Finset.univ.erase (col x)).erase (col y), d :=
              Finset.sum_le_sum fun i _ => hpartsmall i
          _ = (s - 2) * d := by rw [Finset.sum_const, hcardrest, smul_eq_mul]
  10. The total number of vertices is at most sd - r + 2, completing the contradiction.

    Decomposing the total number of vertices into the two cross-edge parts plus the remaining s - 2 parts yields |V(G)| ≤ (2d + 2 - r) + (s - 2)d = sd - r + 2, contradicting the contradiction assumption |V(G)| > sd - r + 2.

    lines 176–182

    uses Finset.add_sum_erase, Nat.add_mul, Nat.sub_add_cancel

      have hsplit : ∑ i, (P i).card = (P (col x)).card + ((P (col y)).card +
          ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card) := by
        rw [← Finset.add_sum_erase _ _ (Finset.mem_univ (col x)),
          ← Finset.add_sum_erase _ _ (Finset.mem_erase.mpr ⟨hnecol.symm, Finset.mem_univ _⟩)]
      have hsd : (s - 2) * d + 2 * d = s * d := by
        rw [← Nat.add_mul, Nat.sub_add_cancel (by omega)]
      omega
cicb_dense
Under the parameter bounds 3 ≤ s, 3r + 3s < d + 10, sd + 3 ≤ n + r, and d + 1 < n, the inequality (3s - 4)n / (3s - 1) < n - 1 - d holds.
Finset.add_sum_erase
A sum of a function over a finite set decomposes into the value at an element a plus the sum over the set with a removed.
Finset.card_sdiff_add_card_inter
For finite sets s and t, |s \ t| + |s ∩ t| = |s|.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum of the cardinalities of its fibers under a map.
Finset.sum_const
The sum of a constant over a finite set equals the cardinality of the set multiplied by the constant.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set, then ∑ i, f(i) ≤ ∑ i, g(i).
lt_of_lt_of_le
In a preorder, a < b and b ≤ c imply a < c.
Nat.add_mul
Distributivity of multiplication over addition on natural numbers: (n + m) * k = n * k + m * k.
Nat.div_lt_iff_lt_mul
For natural numbers with positive k, x / k < y if and only if x < y * k.
Nat.mul_le_mul_right
Multiplication of natural numbers preserves non-strict inequality on the right: if n ≤ m, then n * k ≤ m * k.
Nat.sub_add_cancel
For natural numbers with m ≤ n, (n - m) + m = n.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex equals its degree.
SimpleGraph.colorable_of_cliqueFree_lt_minDegree
A finite simple graph without an (r + 1)-clique and with minimum degree strictly exceeding ((3r - 4) / (3r - 1)) * |V| is r-colorable.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
smul_eq_mul
For natural numbers, scalar multiplication a • b coincides with standard multiplication a * b.

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

theorem cicb_dense (s d r n : ℕ) (hs : 3 ≤ s) (hgap : 3 * r + 3 * s < d + 10)    (hn : s * d + 3 ≤ n + r) (hnd : d + 1 < n) :    (3 * s - 4) * n / (3 * s - 1) < n - 1 - d := by  obtain ⟨a, rfl⟩ : ∃ a, s = a + 3 := ⟨s - 3, by omega⟩  obtain ⟨e, rfl⟩ : ∃ e, n = e + 1 + d := ⟨n - 1 - d, by omega⟩  have h1 : 3 * (a + 3) - 4 = 3 * a + 5 := by omega  have h2 : 3 * (a + 3) - 1 = 3 * a + 8 := by omega  have h3 : e + 1 + d - 1 - d = e := by omega  rw [h1, h2, h3, Nat.div_lt_iff_lt_mul (by omega)]  nlinariththeorem connected_independence_local_clique_card_bound    (r s d : ℕ) (hr : 3 ≤ r) (hs : 3 ≤ s) (hgap : 3 * r + 3 * s < d + 10)    (α : Type) [Fintype α] [DecidableEq α]    (G : SimpleGraph α) [DecidableRel G.Adj]    (hconn : G.Connected) (hindep : G.IndepSetFree (s + 1))    (hdeg : ∀ v, G.degree v ≤ d)    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,      S.card = r ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :    Fintype.card α ≤ s * d - r + 2 := by  classical  letI : Nonempty α := hconn.nonempty  by_contra hn  have h3d : 3 * d ≤ s * d := Nat.mul_le_mul_right d hs  have hn' : s * d + 3 ≤ Fintype.card α + r := by omega  have hnd : d + 1 < Fintype.card α := by omega  have hmin : Fintype.card α - 1 - d ≤ Gᶜ.minDegree := by    apply Gᶜ.le_minDegree_of_forall_le_degree    intro v    rw [G.degree_compl]    have hd := hdeg v    omega  have hf : Gᶜ.CliqueFree (s + 1) := by simpa using hindep  have hdense : (3 * s - 4) * Fintype.card α / (3 * s - 1) < Gᶜ.minDegree :=    lt_of_lt_of_le (cicb_dense s d r _ hs hgap hn' hnd) hmin  have hcolor : Gᶜ.Colorable s :=    SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := s) hf hdense  obtain ⟨col⟩ := hcolor  let P : Fin s → Finset α := fun i => Finset.univ.filter fun x => col x = i  have hmem : ∀ i x, x ∈ P i ↔ col x = i := by intro i x; simp [P]  have hinside : ∀ (i : Fin s) (x : α), x ∈ P i → ∀ y ∈ P i, x ≠ y → G.Adj x y := by    intro i x hx y hy hxy    have hxe := (hmem i x).mp hx    have hye := (hmem i y).mp hy    by_contra h    have hcomp : Gᶜ.Adj x y := ⟨hxy, h⟩    have hncol := col.valid hcomp    exact hncol (hxe.trans hye.symm)  have hsum : ∑ i, (P i).card = Fintype.card α := by    have h := Finset.card_eq_sum_card_fiberwise      (f := fun x : α => col x) (s := Finset.univ) (t := Finset.univ) (by simp)    simpa [P] using h.symm  have hpartcap : ∀ i, (P i).card ≤ d + 1 := by    intro i    by_cases hne : (P i).Nonempty    · obtain ⟨x, hx⟩ := hne      have hsub : (P i).erase x ⊆ G.neighborFinset x := by        intro y hy        have hy' := Finset.mem_erase.mp hy        exact (SimpleGraph.mem_neighborFinset G x y).mpr          (hinside i x hx y hy'.2 hy'.1.symm)      have hc := Finset.card_le_card hsub      have he := Finset.card_erase_add_one hx      rw [SimpleGraph.card_neighborFinset_eq_degree] at hc      have hd := hdeg x      omega    · have he : P i = ∅ := Finset.not_nonempty_iff_eq_empty.mp hne      simp [he]  have hpartsmall : ∀ i, (P i).card ≤ d := by    intro i    by_contra h    have hs' : (P i).card = d + 1 := by have := hpartcap i; omega    have hne : (P i).Nonempty := Finset.card_pos.mp (by omega)    obtain ⟨x, hx⟩ := hne    have hclosed : ∀ u ∈ P i, ∀ v, G.Adj u v → v ∈ P i := by      intro u hu v huv      have hsub : (P i).erase u ⊆ G.neighborFinset u := by        intro z hz        have hz' := Finset.mem_erase.mp hz        exact (SimpleGraph.mem_neighborFinset G u z).mpr          (hinside i u hu z hz'.2 hz'.1.symm)      have he := Finset.card_erase_add_one hu      have hcard : (G.neighborFinset u).card ≤ ((P i).erase u).card := by        rw [SimpleGraph.card_neighborFinset_eq_degree]        have hd := hdeg u        omega      have heq := Finset.eq_of_subset_of_card_le hsub hcard      have hv : v ∈ G.neighborFinset u := (SimpleGraph.mem_neighborFinset G u v).mpr huv      rw [← heq] at hv      exact (Finset.mem_erase.mp hv).2    have hwalk : ∀ {u v}, G.Walk u v → u ∈ P i → v ∈ P i := by      intro u v p      induction p with      | nil => intro hu; exact hu      | cons h p ih => intro hu; exact ih (hclosed _ hu _ h)    have hall : P i = Finset.univ := by      apply Finset.eq_univ_iff_forall.mpr      intro v      obtain ⟨p⟩ := hconn x v      exact hwalk p hx    rw [hall] at hs'    simp at hs'    omega  have hcross : ∃ x y, G.Adj x y ∧ col x ≠ col y := by    by_contra h    push_neg at h    have hwalk : ∀ {u v}, G.Walk u v → col u = col v := by      intro u v p      induction p with      | nil => rfl      | cons hab p ih => exact (h _ _ hab).trans ih    obtain ⟨x⟩ := (inferInstance : Nonempty α)    have hall : P (col x) = Finset.univ := by      apply Finset.eq_univ_iff_forall.mpr      intro v      obtain ⟨p⟩ := hconn x v      exact (hmem _ v).mpr (hwalk p).symm    have := hpartsmall (col x)    rw [hall, Finset.card_univ] at this    omega  obtain ⟨x, y, hxy, hnecol⟩ := hcross  obtain ⟨Q, hQcard, hxQ, hyQ, hQcl⟩ := hclique x y hxy  have hQbound : ∀ i u, u ∈ P i → u ∈ Q →      (P i).card + r ≤ d + 1 + (Q ∩ P i).card := by    intro i u huP huQ    let E := (P i).erase u    let R := Q \ P i    have hdis : Disjoint E R := by      apply Finset.disjoint_left.mpr      intro z hzE hzR      have hzP := (Finset.mem_erase.mp hzE).2      have hznot := (Finset.mem_sdiff.mp hzR).2      exact hznot hzP    have hsub : E ∪ R ⊆ G.neighborFinset u := by      intro z hz      rcases Finset.mem_union.mp hz with hzE | hzR      · have hz' := Finset.mem_erase.mp hzE        exact (SimpleGraph.mem_neighborFinset G u z).mpr          (hinside i u huP z hz'.2 hz'.1.symm)      · have hz' := Finset.mem_sdiff.mp hzR        have hne : u ≠ z := by intro he; subst z; exact hz'.2 huP        exact (SimpleGraph.mem_neighborFinset G u z).mpr (hQcl huQ hz'.1 hne)    have hcard := Finset.card_le_card hsub    rw [SimpleGraph.card_neighborFinset_eq_degree, Finset.card_union_of_disjoint hdis] at hcard    have he := Finset.card_erase_add_one huP    have hr' := Finset.card_sdiff_add_card_inter Q (P i)    have hd := hdeg u    change ((P i).erase u).card + R.card ≤ G.degree u at hcard    change R.card + (Q ∩ P i).card = Q.card at hr'    omega  have hxi : x ∈ P (col x) := (hmem (col x) x).2 rfl  have hyj : y ∈ P (col y) := (hmem (col y) y).2 rfl  have hxbound := hQbound (col x) x hxi hxQ  have hybound := hQbound (col y) y hyj hyQ  have hdis : Disjoint (Q ∩ P (col x)) (Q ∩ P (col y)) := by    apply Finset.disjoint_left.mpr    intro z hz1 hz2    have h1 := (hmem (col x) z).mp (Finset.mem_inter.mp hz1).2    have h2 := (hmem (col y) z).mp (Finset.mem_inter.mp hz2).2    exact hnecol (h1.symm.trans h2)  have hsub : (Q ∩ P (col x)) ∪ (Q ∩ P (col y)) ⊆ Q := by    intro z hz    rcases Finset.mem_union.mp hz with h | h <;> exact (Finset.mem_inter.mp h).1  have hc := Finset.card_le_card hsub  rw [Finset.card_union_of_disjoint hdis, hQcard] at hc  -- the two parts of the cross edge, and at most d in each of the others  have hrest : ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card ≤ (s - 2) * d := by    have hcardrest : ((Finset.univ.erase (col x)).erase (col y)).card = s - 2 := by      rw [Finset.card_erase_of_mem (Finset.mem_erase.mpr ⟨hnecol.symm, Finset.mem_univ _⟩),        Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]      omega    calc ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card        ≤ ∑ _i ∈ (Finset.univ.erase (col x)).erase (col y), d :=          Finset.sum_le_sum fun i _ => hpartsmall i      _ = (s - 2) * d := by rw [Finset.sum_const, hcardrest, smul_eq_mul]  have hsplit : ∑ i, (P i).card = (P (col x)).card + ((P (col y)).card +      ∑ i ∈ (Finset.univ.erase (col x)).erase (col y), (P i).card) := by    rw [← Finset.add_sum_erase _ _ (Finset.mem_univ (col x)),      ← Finset.add_sum_erase _ _ (Finset.mem_erase.mpr ⟨hnecol.symm, Finset.mem_univ _⟩)]  have hsd : (s - 2) * d + 2 * d = s * d := by    rw [← Nat.add_mul, Nat.sub_add_cancel (by omega)]  omega
See it in the graphDiscuss this resultChallenge it