connected_graph_indep_three_degree_42_six_cliques_card_le_122
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.
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.
classical letI : Nonempty α := hconn.nonempty by_contra hn have hn' : 123 ≤ Fintype.card α := by omega
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.
uses
Gᶜ.le_minDegree_of_forall_le_degree,G.degree_complhave 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
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`.
uses
SimpleGraph.colorable_of_cliqueFree_lt_minDegreehave 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
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.
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)
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|.
uses
Finset.card_eq_sum_card_fiberwise,Fin.sum_univ_threehave 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
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.
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.mphave 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]
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.
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.mprhave 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
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.
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
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.
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
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.
uses
Finset.card_pos.mphave 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
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|.
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_interhave 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
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.
uses
Finset.disjoint_left.mpr,Finset.mem_inter.mp,Finset.mem_union.mp,Finset.card_le_card,Finset.card_union_of_disjointhave 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|.
- The key step uses the Andrásfai-Erdős-Sós theorem (formalized in Mathlib as `SimpleGraph.colorable_of_cliqueFree_lt_minDegree`) for r = 3, which states that any triangle-dense or K₄-free graph with minimum degree greater than 5/8 of the vertex count is 3-colorable.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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