AFTD Auto-Formalizing Theoretical Domains

connected_graph_indep_three_degree_42_seven_cliques_card_le_121

theoremverified

A connected finite simple graph with independence number at most three, maximum degree at most 42, and every edge in a seven-vertex clique has at most 121 vertices.

Statement

theorem connected_graph_indep_three_degree_42_seven_cliques_card_le_121
    (α : Type) [Fintype α] [DecidableEq α]
    (G : SimpleGraph α) [DecidableRel G.Adj]
    (hconn : G.Connected) (hindep : G.IndepSetFree 4)
    (hdeg : ∀ v, G.degree v ≤ 42)
    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,
      S.card = 7 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :
    Fintype.card α ≤ 121
Source
Auxiliary-graph refinement for OP-110 using Mathlib SimpleGraph.colorable_of_cliqueFree_lt_minDegree and the seven-vertex out-neighborhood cliques. Experiment 12531 shows the abstract bound is sharp.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by contradiction: assume |α| ≥ 122. Under this assumption, the complement graph Gᶜ has minimum degree δ(Gᶜ) ≥ |α| - 43 > 5|α| / 8 and has no 4-clique, so the Andrásfai-Erdős-Sós theorem guarantees that Gᶜ is 3-colorable. The three color classes form three cliques in G, each having size at most 42 (a size of 43 would make the clique a connected component, contradicting connectedness). Connectedness also forces an edge xy between two distinct color classes, which by assumption lies in a 7-clique Q; however, the degree bound of 42 forces Q to intersect the two color classes in at least 8 vertices altogether, contradicting |Q| = 7.

  1. Assume for contradiction that the graph has at least 122 vertices.

    Since G is connected, the vertex type α is nonempty. We proceed by contradiction: assuming |α| ≤ 121 is false implies |α| ≥ 122.

    lines 12–15

      classical
      letI : Nonempty α := hconn.nonempty
      by_contra hn
      have hn' : 122 ≤ Fintype.card α := by omega
  2. The minimum degree of the complement graph satisfies δ(Gᶜ) ≥ |α| - 43.

    For any vertex v, its degree in the complement graph Gᶜ is |α| - 1 - deg(v). Since deg(v) ≤ 42 for all v, every vertex in Gᶜ has degree at least |α| - 43. By Gᶜ.le_minDegree_of_forall_le_degree, the minimum degree δ(Gᶜ) is at least |α| - 43.

    lines 16–21

    uses Gᶜ.le_minDegree_of_forall_le_degree, G.degree_compl

      have hmin : Fintype.card α - 43 ≤ Gᶜ.minDegree := by
        apply Gᶜ.le_minDegree_of_forall_le_degree
        intro v
        rw [G.degree_compl]
        have hd := hdeg v
        omega
  3. The complement graph Gᶜ is 3-colorable.

    Since G contains no independent set of size 4, the complement graph Gᶜ contains no clique of size 4 (Gᶜ.CliqueFree 4). With |α| ≥ 122 and δ(Gᶜ) ≥ |α| - 43, linear arithmetic verifies that (3 × 3 - 4)|α| / (3 × 3 - 1) = 5|α| / 8 < δ(Gᶜ). By the Andrásfai-Erdős-Sós theorem (SimpleGraph.colorable_of_cliqueFree_lt_minDegree with r = 3), Gᶜ is 3-colorable.

    lines 22–26

    uses SimpleGraph.colorable_of_cliqueFree_lt_minDegree

      have hf : Gᶜ.CliqueFree 4 := by simpa using hindep
      have hdense : (3 * 3 - 4) * Fintype.card α / (3 * 3 - 1) < Gᶜ.minDegree := by
        omega
      have hcolor : Gᶜ.Colorable 3 :=
        SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := 3) hf hdense
  4. The 3-coloring of Gᶜ partitions the vertices into three cliques P₀, P₁, P₂ in G.

    Fix a proper 3-coloring col : α → Fin 3 of Gᶜ, and define each color class P(i) as the set of vertices of color i. Since col is a proper coloring of Gᶜ, no two vertices in P(i) are adjacent in Gᶜ. Therefore, any two distinct vertices in the same P(i) must be adjacent in G, meaning each P(i) is a clique in G.

    lines 27–37

      obtain ⟨col⟩ := hcolor
      let P : Fin 3 → 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 3) (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)
  5. The sum of the sizes of the three parts is |α|.

    Partitioning the universe of vertices fiberwise according to col expresses the total number of vertices as |P(0)| + |P(1)| + |P(2)| = |α|.

    lines 38–41

    uses Finset.card_eq_sum_card_fiberwise, Fin.sum_univ_three

      have hsum : (P 0).card + (P 1).card + (P 2).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, Fin.sum_univ_three] using h.symm
  6. Each part has size at most 43: |P(i)| ≤ 43.

    If P(i) is nonempty, take any vertex x ∈ P(i). Since P(i) is a clique in G, all other vertices of P(i) are neighbors of x in G, so |P(i)| - 1 ≤ deg(x) ≤ 42, which implies |P(i)| ≤ 43. If P(i) is empty, its size is 0 ≤ 43.

    lines 42–57

    uses SimpleGraph.mem_neighborFinset, Finset.card_le_card, Finset.card_erase_add_one, SimpleGraph.card_neighborFinset_eq_degree, Finset.not_nonempty_iff_eq_empty.mp, Finset.mem_erase.mp

      have hpartcap : ∀ i, (P i).card ≤ 43 := 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]
  7. Each part has size at most 42: |P(i)| ≤ 42.

    Suppose |P(i)| = 43. For any vertex u ∈ P(i), the 42 other vertices in P(i) are neighbors of u, already saturating its maximum degree deg(u) ≤ 42. Thus the neighborhood of u in G is exactly P(i) \ {u}, meaning no edges leave P(i). By induction on walks, any vertex reachable from P(i) must lie in P(i). Since G is connected, every vertex is reachable from P(i), forcing P(i) = α and |α| = 43, which contradicts |α| ≥ 122.

    lines 58–92

    uses Finset.card_pos.mp, SimpleGraph.mem_neighborFinset, Finset.mem_erase.mp, Finset.card_erase_add_one, SimpleGraph.card_neighborFinset_eq_degree, Finset.eq_of_subset_of_card_le, Finset.eq_univ_iff_forall.mpr

      have hpartsmall : ∀ i, (P i).card ≤ 42 := by
        intro i
        by_contra h
        have hs : (P i).card = 43 := 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
  8. Each part has size at least 38: |P(i)| ≥ 38.

    Since the three parts sum to |α| ≥ 122 and each of the other two parts has size at most 42, the remaining part has size at least 122 - 42 - 42 = 38.

    lines 93–101

      have hpartlower : ∀ i, 38 ≤ (P i).card := by
        intro i
        have h0 := hpartsmall 0
        have h1 := hpartsmall 1
        have h2 := hpartsmall 2
        fin_cases i
        · change 38 ≤ (P 0).card; omega
        · change 38 ≤ (P 1).card; omega
        · change 38 ≤ (P 2).card; omega
  9. Any two distinct parts have combined size at least 80: |P(i)| + |P(j)| ≥ 80.

    For i ≠ j, the third part has size at most 42, so |P(i)| + |P(j)| = |α| - |P(k)| ≥ 122 - 42 = 80.

    lines 102–116

      have hpair : ∀ i j : Fin 3, i ≠ j → 80 ≤ (P i).card + (P j).card := by
        intro i j hij
        have h0 := hpartsmall 0
        have h1 := hpartsmall 1
        have h2 := hpartsmall 2
        fin_cases i <;> fin_cases j
        · exact (hij rfl).elim
        · change 80 ≤ (P 0).card + (P 1).card; omega
        · change 80 ≤ (P 0).card + (P 2).card; omega
        · change 80 ≤ (P 1).card + (P 0).card; omega
        · exact (hij rfl).elim
        · change 80 ≤ (P 1).card + (P 2).card; omega
        · change 80 ≤ (P 2).card + (P 0).card; omega
        · change 80 ≤ (P 2).card + (P 1).card; omega
        · exact (hij rfl).elim
  10. There exists an edge in G between two vertices of different colors.

    If every edge of G joined vertices of the same color, color would be constant along any walk in G. Because G is connected, all vertices would have the same color. However, P(0) and P(1) each have at least 38 vertices and are thus both nonempty, so vertices of both color 0 and color 1 exist. Hence there must be an edge xy in G with col(x) ≠ col(y).

    lines 117–134

    uses Finset.card_pos.mp

      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
        have h0 : (P 0).Nonempty := Finset.card_pos.mp (by have := hpartlower 0; omega)
        have h1 : (P 1).Nonempty := Finset.card_pos.mp (by have := hpartlower 1; omega)
        obtain ⟨x, hx⟩ := h0
        obtain ⟨y, hy⟩ := h1
        obtain ⟨p⟩ := hconn x y
        have hh := hwalk p
        have hx' := (hmem 0 x).mp hx
        have hy' := (hmem 1 y).mp hy
        rw [hx', hy'] at hh
        exact (by decide : (0 : Fin 3) ≠ 1) hh
  11. For any vertex u ∈ P(i) lying in a 7-clique Q, |P(i)| + 7 ≤ 43 + |Q ∩ P(i)|.

    The neighbors of u in G contain both P(i) \ {u} (since P(i) is a clique) and Q \ P(i) (since Q is a clique). These two sets are disjoint subsets of the neighborhood of u. Therefore, deg(u) ≥ (|P(i)| - 1) + (|Q| - |Q ∩ P(i)|) = |P(i)| + 6 - |Q ∩ P(i)|. Since deg(u) ≤ 42, rearranging gives |P(i)| + 7 ≤ 43 + |Q ∩ P(i)| (or equivalently, |Q ∩ P(i)| ≥ |P(i)| - 36).

    lines 135–164

    uses Finset.disjoint_left.mpr, Finset.mem_erase.mp, Finset.mem_sdiff.mp, Finset.mem_union.mp, SimpleGraph.mem_neighborFinset, Finset.card_le_card, SimpleGraph.card_neighborFinset_eq_degree, Finset.card_union_of_disjoint, Finset.card_erase_add_one, Finset.card_sdiff_add_card_inter

      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 + 7 ≤ 43 + (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
  12. The 7-clique Q on the cross-edge xy must contain at least 8 vertices, a contradiction.

    By the edge-clique hypothesis, the cross-edge xy lies in a 7-clique Q. Applying the intersection lower bound to x ∈ P(col(x)) ∩ Q and y ∈ P(col(y)) ∩ Q gives |Q ∩ P(col(x))| ≥ |P(col(x))| - 36 and |Q ∩ P(col(y))| ≥ |P(col(y))| - 36. Since col(x) ≠ col(y), these two intersections are disjoint subsets of Q. Hence |Q| ≥ |Q ∩ P(col(x))| + |Q ∩ P(col(y))| ≥ |P(col(x))| + |P(col(y))| - 72 ≥ 80 - 72 = 8, contradicting |Q| = 7. Linear arithmetic via omega closes the contradiction.

    lines 165–181

    uses Finset.disjoint_left.mpr, Finset.mem_inter.mp, Finset.card_le_card, 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 hpairs := hpair (col x) (col y) hnecol
      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
      omega
Gᶜ.le_minDegree_of_forall_le_degree
If every vertex in a graph has degree at least k, then the minimum degree of the graph is at least k.
G.degree_compl
In a finite graph, the degree of a vertex in the complement graph is the total number of vertices minus 1 minus its degree in the original graph.
SimpleGraph.colorable_of_cliqueFree_lt_minDegree
A K_{r+1}-free graph with minimum degree strictly greater than (3r - 4)n / (3r - 1) is r-colorable (the Andrásfai-Erdős-Sós theorem).
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of the fibers of any map defined on it.
Fin.sum_univ_three
A sum indexed over Fin 3 equals the sum of the values at 0, 1, and 2.
SimpleGraph.mem_neighborFinset
A vertex belongs to the neighbor finset of another vertex if and only if they are adjacent in the graph.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the other's.
Finset.card_erase_add_one
Erasing an element from a finite set yields a set whose cardinality plus one is the original cardinality.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex equals its degree.
Finset.not_nonempty_iff_eq_empty.mp
A finite set is empty if and only if it is not nonempty.
Finset.mem_erase.mp
If an element belongs to a set with a point removed, it is distinct from that point and belongs to the original set.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.eq_of_subset_of_card_le
If a subset of a finite set has cardinality at least that of the superset, the two sets are equal.
Finset.eq_univ_iff_forall.mpr
A finset in a finite type is the universal set if it contains every element of the type.
Finset.disjoint_left.mpr
Two sets are disjoint if no element of the first set belongs to the second set.
Finset.mem_sdiff.mp
An element of a set difference belongs to the first set and does not belong to the second set.
Finset.mem_union.mp
An element of a union of two sets belongs to at least one of the sets.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_sdiff_add_card_inter
For any two finite sets, the size of their difference plus the size of their intersection equals the size of the first set.
Finset.mem_inter.mp
An element of an intersection of two sets belongs to both sets.

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

set_option maxRecDepth 100000set_option maxHeartbeats 0theorem connected_graph_indep_three_degree_42_seven_cliques_card_le_121    (α : Type) [Fintype α] [DecidableEq α]    (G : SimpleGraph α) [DecidableRel G.Adj]    (hconn : G.Connected) (hindep : G.IndepSetFree 4)    (hdeg : ∀ v, G.degree v ≤ 42)    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,      S.card = 7 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :    Fintype.card α ≤ 121 := by  classical  letI : Nonempty α := hconn.nonempty  by_contra hn  have hn' : 122 ≤ Fintype.card α := by omega  have hmin : Fintype.card α - 43 ≤ 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 4 := by simpa using hindep  have hdense : (3 * 3 - 4) * Fintype.card α / (3 * 3 - 1) < Gᶜ.minDegree := by    omega  have hcolor : Gᶜ.Colorable 3 :=    SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := 3) hf hdense  obtain ⟨col⟩ := hcolor  let P : Fin 3 → 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 3) (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 : (P 0).card + (P 1).card + (P 2).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, Fin.sum_univ_three] using h.symm  have hpartcap : ∀ i, (P i).card ≤ 43 := 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 ≤ 42 := by    intro i    by_contra h    have hs : (P i).card = 43 := 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 hpartlower : ∀ i, 38 ≤ (P i).card := by    intro i    have h0 := hpartsmall 0    have h1 := hpartsmall 1    have h2 := hpartsmall 2    fin_cases i    · change 38 ≤ (P 0).card; omega    · change 38 ≤ (P 1).card; omega    · change 38 ≤ (P 2).card; omega  have hpair : ∀ i j : Fin 3, i ≠ j → 80 ≤ (P i).card + (P j).card := by    intro i j hij    have h0 := hpartsmall 0    have h1 := hpartsmall 1    have h2 := hpartsmall 2    fin_cases i <;> fin_cases j    · exact (hij rfl).elim    · change 80 ≤ (P 0).card + (P 1).card; omega    · change 80 ≤ (P 0).card + (P 2).card; omega    · change 80 ≤ (P 1).card + (P 0).card; omega    · exact (hij rfl).elim    · change 80 ≤ (P 1).card + (P 2).card; omega    · change 80 ≤ (P 2).card + (P 0).card; omega    · change 80 ≤ (P 2).card + (P 1).card; omega    · exact (hij rfl).elim  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    have h0 : (P 0).Nonempty := Finset.card_pos.mp (by have := hpartlower 0; omega)    have h1 : (P 1).Nonempty := Finset.card_pos.mp (by have := hpartlower 1; omega)    obtain ⟨x, hx⟩ := h0    obtain ⟨y, hy⟩ := h1    obtain ⟨p⟩ := hconn x y    have hh := hwalk p    have hx' := (hmem 0 x).mp hx    have hy' := (hmem 1 y).mp hy    rw [hx', hy'] at hh    exact (by decide : (0 : Fin 3) ≠ 1) hh  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 + 7 ≤ 43 + (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 hpairs := hpair (col x) (col y) hnecol  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  omega
See it in the graphDiscuss this resultChallenge it