import Mathlib theorem erdos_task : open Filter in ∀ {V : Type*} (G : SimpleGraph V) (hG : G.chromaticNumber = ⊤) (n : ℕ) (hn : 1 ≤ n), ∃ H : G.Subgraph, H.verts.Finite ∧ H.coe.chromaticNumber = (n : ℕ∞) := by intro V G hG n hn obtain ⟨k, rfl⟩ : ∃ k, n = k + 1 := ⟨n - 1, by omega⟩ have hnc : ¬ G.Colorable k := by intro h have := h.chromaticNumber_le rw [hG] at this exact absurd this (by simp) have hex : ∃ H : G.Subgraph, H.verts.Finite ∧ ¬ H.coe.Colorable k := by by_contra hcon push Not at hcon apply hnc exact SimpleGraph.nonempty_hom_of_forall_finite_subgraph_hom (F := (⊤ : SimpleGraph (Fin k))) (fun H hH => (hcon H hH).some) classical have P : ∃ m, ∃ H : G.Subgraph, H.verts.Finite ∧ H.verts.ncard = m ∧ ¬ H.coe.Colorable k := by obtain ⟨H, h1, h2⟩ := hex exact ⟨_, H, h1, rfl, h2⟩ obtain ⟨H, hfin, hcard, hH⟩ := Nat.find_spec P have hmin := fun m (hm : m < Nat.find P) => Nat.find_min P hm refine ⟨H, hfin, ?_⟩ push_cast rw [SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable] refine ⟨?_, hH⟩ obtain ⟨v, hv⟩ : H.verts.Nonempty := by rw [Set.nonempty_iff_ne_empty] intro he apply hH have : IsEmpty H.verts := by rw [he]; infer_instance exact SimpleGraph.Colorable.of_isEmpty _ |>.mono (Nat.zero_le _) set H' := H.deleteVerts {v} with hH' have hsub : H'.verts ⊆ H.verts := by simp [hH'] have hlt : H'.verts.ncard < Nat.find P := by rw [← hcard] apply Set.ncard_lt_ncard _ hfin refine ⟨hsub, fun h => ?_⟩ have := h hv simp [hH'] at this have hc' : H'.coe.Colorable k := by have := hmin _ hlt push Not at this exact this H' (hfin.subset hsub) rfl obtain ⟨c⟩ := hc' have hmem : ∀ w : H.verts, w.1 ≠ v → w.1 ∈ H'.verts := by intro w hw simp [hH', hw, w.2] refine ⟨SimpleGraph.Coloring.mk (fun w => if h : w.1 = v then Fin.last k else (c ⟨w.1, hmem w h⟩).castSucc) ?_⟩ intro a b hab have hab' : H.Adj a.1 b.1 := hab by_cases ha : a.1 = v <;> by_cases hb : b.1 = v · exact absurd (ha.trans hb.symm) hab'.ne · simp [ha, hb, Fin.ext_iff] omega · simp [ha, hb, Fin.ext_iff] omega · simp only [ha, hb, dite_false] intro he have := c.valid (v := ⟨a.1, hmem a ha⟩) (w := ⟨b.1, hmem b hb⟩) (by show H'.Adj a.1 b.1 simp [hH', ha, hb, hab', a.2, b.2]) exact this (Fin.castSucc_injective _ he)