connected_graph_indep_three_degree_42_seven_cliques_card_le_121
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
- digraph_common_predecessor_balanced_seven_card_le_121A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has…
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.
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.
classical letI : Nonempty α := hconn.nonempty by_contra hn have hn' : 122 ≤ Fintype.card α := by omega
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.
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 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.
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
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.
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)
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)| = |α|.
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 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.
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.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 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.
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.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 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.
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
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.
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
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).
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
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).
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_interobtain ⟨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
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.
uses
Finset.disjoint_left.mpr,Finset.mem_inter.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- 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.
- The proof relies on the Andrásfai-Erdős-Sós theorem (`SimpleGraph.colorable_of_cliqueFree_lt_minDegree`), which states that a $K_{r+1}$-free graph on $n$ vertices with minimum degree strictly greater than $\frac{3r-4}{3r-1}n$ is $r$-colorable. Linear inequalities over natural numbers are solved throughout by the `omega` tactic.
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_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