import Mathlib open SimpleGraph lemma c4_of {V : Type} (H : SimpleGraph V) (x y u w : V) (hxy : x ≠ y) (huw : u ≠ w) (h1 : H.Adj x u) (h2 : H.Adj u y) (h3 : H.Adj y w) (h4 : H.Adj w x) : cycleGraph 4 ⊑ H := by refine ⟨⟨⟨![x, u, y, w], ?_⟩, ?_⟩⟩ · intro i j h have hc : ∀ i j : Fin 4, (cycleGraph 4).Adj i j → (i = 0 ∧ j = 1) ∨ (i = 1 ∧ j = 0) ∨ (i = 1 ∧ j = 2) ∨ (i = 2 ∧ j = 1) ∨ (i = 2 ∧ j = 3) ∨ (i = 3 ∧ j = 2) ∨ (i = 3 ∧ j = 0) ∨ (i = 0 ∧ j = 3) := by decide rcases hc i j h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ all_goals simp [h1, h2, h3, h4, h1.symm, h2.symm, h3.symm, h4.symm] · intro i j h have := h1.ne; have := h2.ne; have := h3.ne; have := h4.ne fin_cases i <;> fin_cases j <;> simp_all [eq_comm] lemma le_one_add_choose (d : ℕ) : d ≤ 1 + d.choose 2 := by cases d with | zero => simp | succ d => rw [Nat.choose_succ_succ, Nat.choose_one_right]; omega theorem erdos_task : open SimpleGraph in ∀ (n : ℕ), ((completeBipartiteGraph (Fin n) (Fin (n ^ 2))).edgeSet.ncard = n ^ 3) ∧ ∀ H ≤ completeBipartiteGraph (Fin n) (Fin (n ^ 2)), n ^ 2 + n.choose 2 < H.edgeSet.ncard → cycleGraph 4 ⊑ H := by intro n refine ⟨?_, ?_⟩ · rw [Set.ncard_def, encard_edgeSet_completeBipartiteGraph] simp [ENat.card_eq_coe_fintype_card] rw [← Nat.cast_pow, ENat.toNat_natCast] ring intro H hle hcard classical by_contra hfree set s : Finset (Fin n ⊕ Fin (n ^ 2)) := Finset.univ.map Function.Embedding.inl with hs set t : Finset (Fin n ⊕ Fin (n ^ 2)) := Finset.univ.map Function.Embedding.inr with ht have hbip : H.IsBipartiteWith (s : Set _) (t : Set _) := by refine ⟨?_, ?_⟩ · rw [Finset.disjoint_coe, Finset.disjoint_left] intro a ha hb simp [hs, ht] at ha hb obtain ⟨x, rfl⟩ := ha obtain ⟨y, hy⟩ := hb cases hy · intro v w hvw have := hle hvw cases v <;> cases w <;> simp_all rw [← SimpleGraph.coe_edgeFinset, Set.ncard_coe_finset, ← isBipartiteWith_sum_degrees_eq_card_edges' hbip, ht, Finset.sum_map] at hcard have hN : ∀ b : Fin (n ^ 2), H.neighborFinset (Sum.inr b) ⊆ s := fun b => isBipartiteWith_neighborFinset_subset' hbip (by simp [ht]) have hdisj : (Set.univ : Set (Fin (n ^ 2))).PairwiseDisjoint (fun b => (H.neighborFinset (Sum.inr b)).powersetCard 2) := by intro b _ b' _ hbb' rw [Function.onFun, Finset.disjoint_left] intro P hP hP' rw [Finset.mem_powersetCard] at hP hP' obtain ⟨x, y, hxy, rfl⟩ := Finset.card_eq_two.mp hP.2 have mx : x ∈ ({x, y} : Finset _) := by simp have my : y ∈ ({x, y} : Finset _) := by simp have hx := hP.1 mx have hy := hP.1 my have hx' := hP'.1 mx have hy' := hP'.1 my rw [mem_neighborFinset] at hx hy hx' hy' exact hfree (c4_of H x y (Sum.inr b) (Sum.inr b') hxy (by simpa using hbb') hx.symm hy hy'.symm hx') have hsum : ∑ b : Fin (n ^ 2), (H.degree (Sum.inr b)).choose 2 ≤ n.choose 2 := by calc ∑ b : Fin (n ^ 2), (H.degree (Sum.inr b)).choose 2 = ∑ b : Fin (n ^ 2), ((H.neighborFinset (Sum.inr b)).powersetCard 2).card := by simp [Finset.card_powersetCard] _ = (Finset.univ.biUnion (fun b => (H.neighborFinset (Sum.inr b)).powersetCard 2)).card := by rw [Finset.card_biUnion] simpa using hdisj _ ≤ (s.powersetCard 2).card := by apply Finset.card_le_card intro P hP simp only [Finset.mem_biUnion, Finset.mem_univ, true_and] at hP obtain ⟨b, hb⟩ := hP rw [Finset.mem_powersetCard] at hb ⊢ exact ⟨hb.1.trans (hN b), hb.2⟩ _ = n.choose 2 := by simp [Finset.card_powersetCard, hs] have : ∑ b : Fin (n ^ 2), H.degree (Sum.inr b) ≤ n ^ 2 + n.choose 2 := by calc ∑ b : Fin (n ^ 2), H.degree (Sum.inr b) ≤ ∑ b : Fin (n ^ 2), (1 + (H.degree (Sum.inr b)).choose 2) := Finset.sum_le_sum (fun b _ => le_one_add_choose _) _ = n ^ 2 + ∑ b : Fin (n ^ 2), (H.degree (Sum.inr b)).choose 2 := by rw [Finset.sum_add_distrib]; simp _ ≤ n ^ 2 + n.choose 2 := by omega exact absurd (lt_of_lt_of_le hcard this) (lt_irrefl _)