AFTD Auto-Formalizing Theoretical Domains

connected_graph_indep_three_degree_42_six_cliques_card_le_122

theoremverified

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

Statement

theorem connected_graph_indep_three_degree_42_six_cliques_card_le_122
    (α : 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 = 6 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :
    Fintype.card α ≤ 122
Source
Six-clique version of the auxiliary graph bound for OP-110.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

Assume for contradiction that the graph G has at least 123 vertices. Since the maximum degree in G is at most 42, the complement graph Gᶜ has minimum degree δ(Gᶜ) ≥ |V| - 43 > 5|V|/8, and since G has no independent set of size 4, Gᶜ is K₄-free; by the Andrásfai-Erdős-Sós theorem, Gᶜ is 3-colorable, partitioning V into three cliques P 0, P 1, P 2 in G. Degree and connectivity arguments show each color class has size between 39 and 42, so any two sum to at least 81. Finally, connectivity yields an edge between distinct color classes, which belongs to a 6-clique Q; bounding the degrees of the edge's endpoints within Q and their color classes forces the sum of those two color classes to be at most 80, a contradiction.

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

    We proceed by contradiction (`by_contra hn`). If the vertex count |V| is not at most 122, then |V| ≥ 123.

    lines 12–15

      classical
      letI : Nonempty α := hconn.nonempty
      by_contra hn
      have hn' : 123 ≤ Fintype.card α := by omega
  2. The complement graph Gᶜ has minimum degree at least |V| - 43.

    By `Gᶜ.le_minDegree_of_forall_le_degree`, it suffices to verify that every vertex v has degree at least |V| - 43 in Gᶜ. Rewriting with `G.degree_compl`, the degree in the complement is |V| - 1 - deg_G(v). Since deg_G(v) ≤ 42 for every vertex, linear arithmetic yields deg_{Gᶜ}(v) ≥ |V| - 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 has no independent set of size 4 (`hindep`), the complement Gᶜ contains no clique of size 4 (`hf`). Because |V| ≥ 123 and δ(Gᶜ) ≥ |V| - 43, linear arithmetic establishes that 5|V|/8 = ⌊(3 · 3 - 4)|V| / (3 · 3 - 1)⌋ < δ(Gᶜ) (`hdense`). Applying the Andrásfai-Erdős-Sós theorem (`SimpleGraph.colorable_of_cliqueFree_lt_minDegree` with r = 3) proves that Gᶜ is 3-colorable, yielding a proper 3-coloring `col`.

    lines 22–27

    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
      obtain ⟨col⟩ := hcolor
  4. Each of the three color classes of Gᶜ induces a clique in G.

    We partition the vertex set into the three color classes P 0, P 1, P 2 according to `col`. If two distinct vertices x, y belong to the same color class P i, they have the same color under `col`. Since `col` is a proper coloring of Gᶜ, x and y cannot be adjacent in Gᶜ, which means they must be adjacent in the original graph G.

    lines 28–37

      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 color classes equals |V|.

    Using `Finset.card_eq_sum_card_fiberwise` applied to `col`, the total number of vertices is the sum of the fiber sizes over the three colors, which `Fin.sum_univ_three` evaluates as |P 0| + |P 1| + |P 2| = |V|.

    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 color class has size at most 43.

    If a color class P i is empty, its cardinality is 0 ≤ 43. If P i is nonempty, pick any vertex x ∈ P i. Because P i induces a clique in G, every other vertex of P i is a neighbor of x in G, so (P i).erase x ⊆ N_G(x). Comparing cardinalities shows |P i| - 1 ≤ deg_G(x) ≤ 42, which implies |P i| ≤ 43.

    lines 42–57

    uses Finset.mem_erase.mp, SimpleGraph.mem_neighborFinset, Finset.card_le_card, Finset.card_erase_add_one, SimpleGraph.card_neighborFinset_eq_degree, Finset.not_nonempty_iff_eq_empty.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 color class has size at most 42.

    Suppose for contradiction that some |P i| = 43. For every vertex u ∈ P i, its 42 other members in P i all lie in N_G(u). Because deg_G(u) ≤ 42, N_G(u) must equal exactly (P i).erase u by `Finset.eq_of_subset_of_card_le`. Thus no edge in G leaves P i. By induction on walks, any vertex connected to a vertex in P i must remain in P i. Since G is connected (`hconn`), this would force P i = V, giving |V| = 43, which contradicts |V| ≥ 123.

    lines 58–92

    uses Finset.card_pos.mp, Finset.mem_erase.mp, SimpleGraph.mem_neighborFinset, 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 color class has size at least 39.

    Since the sum of the three sizes is |V| ≥ 123 and each of the other two parts has size at most 42, any given part P i must have size |P i| = |V| - ∑_{j ≠ i} |P j| ≥ 123 - 2 · 42 = 39. A case split on i in Fin 3 followed by linear arithmetic closes each case.

    lines 93–101

      have hpartlower : ∀ i, 39 ≤ (P i).card := by
        intro i
        have h0 := hpartsmall 0
        have h1 := hpartsmall 1
        have h2 := hpartsmall 2
        fin_cases i
        · change 39 ≤ (P 0).card; omega
        · change 39 ≤ (P 1).card; omega
        · change 39 ≤ (P 2).card; omega
  9. The sum of the sizes of any two distinct color classes is at least 81.

    For any distinct colors i ≠ j, the remaining color class has size at most 42, so |P i| + |P j| = |V| - |P k| ≥ 123 - 42 = 81. Case analysis over all pairs in Fin 3 and linear arithmetic verifies this.

    lines 102–116

      have hpair : ∀ i j : Fin 3, i ≠ j → 81 ≤ (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 81 ≤ (P 0).card + (P 1).card; omega
        · change 81 ≤ (P 0).card + (P 2).card; omega
        · change 81 ≤ (P 1).card + (P 0).card; omega
        · exact (hij rfl).elim
        · change 81 ≤ (P 1).card + (P 2).card; omega
        · change 81 ≤ (P 2).card + (P 0).card; omega
        · change 81 ≤ (P 2).card + (P 1).card; omega
        · exact (hij rfl).elim
  10. There exists an edge xy in G between two different color classes, and it is contained in a 6-clique Q.

    If every edge in G joined vertices of the same color, then by connectivity all vertices in G would share the same color. This contradicts the fact that at least two color classes (e.g., P 0 and P 1) are nonempty since their sizes are at least 39. Thus there is an edge xy with col(x) ≠ col(y). By hypothesis `hclique`, xy is contained in a 6-clique Q in G.

    lines 117–136

    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
      obtain ⟨x, y, hxy, hnecol⟩ := hcross
      obtain ⟨Q, hQcard, hxQ, hyQ, hQcl⟩ := hclique x y hxy
  11. For any vertex u in Q ∩ P i, the size of P i satisfies |P i| + 6 ≤ 43 + |Q ∩ P i|.

    Let E = (P i).erase u and R = Q \ P i. Because both P i and Q are cliques in G containing u, all elements of E and R are neighbors of u in G. Since E and R are disjoint, their union has size |E| + |R| ≤ deg_G(u) ≤ 42. Since |E| = |P i| - 1 and |R| = |Q| - |Q ∩ P i| = 6 - |Q ∩ P i|, we have (|P i| - 1) + (6 - |Q ∩ P i|) ≤ 42, which rearranges to |P i| + 6 ≤ 43 + |Q ∩ P i|.

    lines 137–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

      have hQbound : ∀ i u, u ∈ P i → u ∈ Q →
          (P i).card + 6 ≤ 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 two color classes containing x and y sum to at most 80, contradicting the lower bound of 81.

    Applying the previous bound to x ∈ Q ∩ P(col x) and y ∈ Q ∩ P(col y) and adding them yields |P(col x)| + |P(col y)| + 12 ≤ 86 + |Q ∩ P(col x)| + |Q ∩ P(col y)|. Since col(x) ≠ col(y), these two intersections are disjoint subsets of Q, so their combined size is at most |Q| = 6. Thus |P(col x)| + |P(col y)| + 12 ≤ 86 + 6 = 92, meaning |P(col x)| + |P(col y)| ≤ 80. However, the sum of any two distinct color classes is at least 81, a contradiction that closes the proof.

    lines 165–181

    uses Finset.disjoint_left.mpr, Finset.mem_inter.mp, Finset.mem_union.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
A graph has minimum degree at least k if every vertex has degree at least k.
G.degree_compl
In the complement of a simple graph on a finite vertex set V, the degree of a vertex v is |V| - 1 - deg(v).
SimpleGraph.colorable_of_cliqueFree_lt_minDegree
Andrásfai-Erdős-Sós theorem: if a simple graph is (r + 1)-clique free and has minimum degree strictly greater than (3r - 4)|V| / (3r - 1), then it is r-colorable.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of the fibers of any mapping on it.
Fin.sum_univ_three
The sum of a function over the three-element type Fin 3 equals f(0) + f(1) + f(2).
Finset.mem_erase.mp
If an element belongs to a finset with an element removed (s.erase a), then it is not equal to a and belongs to s.
SimpleGraph.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_erase_add_one
Removing an element from a finite set decreases its cardinality by one.
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.card_pos.mp
A finite set is nonempty if and only if its cardinality is strictly positive.
Finset.eq_of_subset_of_card_le
If a finite set is a subset of another and has at least the same cardinality, the two sets are equal.
Finset.eq_univ_iff_forall.mpr
A finite subset of a fintype equals the universal finset if every element belongs to it.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second set.
Finset.mem_sdiff.mp
If an element belongs to the set difference s \ t, then it belongs to s and not to t.
Finset.mem_union.mp
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_inter.mp
An element belongs to the intersection of two finite sets if and only if it belongs to both 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 s and t, |s \ t| + |s ∩ t| = |s|.

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_six_cliques_card_le_122    (α : 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 = 6 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α)) :    Fintype.card α ≤ 122 := by  classical  letI : Nonempty α := hconn.nonempty  by_contra hn  have hn' : 123 ≤ 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, 39 ≤ (P i).card := by    intro i    have h0 := hpartsmall 0    have h1 := hpartsmall 1    have h2 := hpartsmall 2    fin_cases i    · change 39 ≤ (P 0).card; omega    · change 39 ≤ (P 1).card; omega    · change 39 ≤ (P 2).card; omega  have hpair : ∀ i j : Fin 3, i ≠ j → 81 ≤ (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 81 ≤ (P 0).card + (P 1).card; omega    · change 81 ≤ (P 0).card + (P 2).card; omega    · change 81 ≤ (P 1).card + (P 0).card; omega    · exact (hij rfl).elim    · change 81 ≤ (P 1).card + (P 2).card; omega    · change 81 ≤ (P 2).card + (P 0).card; omega    · change 81 ≤ (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 + 6 ≤ 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