import Mathlib open SimpleGraph Classical lemma c4_free_of {V : Type} (H : SimpleGraph V) (h : ∀ a b c d : V, H.Adj a b → H.Adj b c → H.Adj c d → H.Adj d a → a ≠ c → b ≠ d → False) : (cycleGraph 4).Free H := by rintro ⟨f⟩ have hadj : ∀ i j : Fin 4, (cycleGraph 4).Adj i j → H.Adj (f i) (f j) := fun i j hij => f.toHom.map_adj hij refine h (f 0) (f 1) (f 2) (f 3) (hadj _ _ (by decide)) (hadj _ _ (by decide)) (hadj _ _ (by decide)) (hadj _ _ (by decide)) ?_ ?_ · intro e; have := f.injective e; exact absurd this (by decide) · intro e; have := f.injective e; exact absurd this (by decide) lemma real_aux (m k : ℕ) (h : m ≤ (2 * k) ^ 2) : (1/2 : ℝ) * (m : ℝ) ^ (1 / 2 : ℝ) ≤ (k : ℝ) := by rw [← Real.sqrt_eq_rpow] have : Real.sqrt m ≤ Real.sqrt ((2 * (k:ℝ)) ^ 2) := Real.sqrt_le_sqrt (by exact_mod_cast h) rw [Real.sqrt_sq (by positivity)] at this linarith theorem erdos_task : open SimpleGraph in ∃ c > (0 : ℝ), ∀ (V : Type) [Fintype V] (G : SimpleGraph V), ∃ H ≤ G, (cycleGraph 4).Free H ∧ c * (G.edgeSet.ncard : ℝ) ^ (1 / 2 : ℝ) ≤ (H.edgeSet.ncard : ℝ) := by refine ⟨1/2, by norm_num, ?_⟩ intro V _ G by_cases hV : Nonempty V swap · rw [not_nonempty_iff] at hV refine ⟨G, le_rfl, ?_, ?_⟩ · exact c4_free_of G (fun a => isEmptyElim a) · have : G.edgeSet = ∅ := by ext e; induction e using Sym2.ind with | h a b => exact isEmptyElim a rw [this]; simp obtain ⟨v, -, hv⟩ := Finset.exists_max_image Finset.univ (fun x => G.degree x) Finset.univ_nonempty simp only [Finset.mem_univ, true_implies] at hv let S : SimpleGraph V := { Adj := fun a b => G.Adj a b ∧ (a = v ∨ b = v) symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨fun _ h => G.irrefl h.1⟩ } have hSG : S ≤ G := fun a b h => h.1 have hSfree : (cycleGraph 4).Free S := by apply c4_free_of intro a b c d hab hbc hcd hda hac hbd have n1 : a ≠ b := hab.1.ne have n3 : c ≠ d := hcd.1.ne rcases hbc.2 with h2 | h2 <;> rcases hda.2 with h4 | h4 · exact hbd (h2.trans h4.symm) · exact n1 (h4.trans h2.symm) · exact n3 (h2.trans h4.symm) · exact hac (h4.trans h2.symm) have hSedge : S.edgeSet = G.incidenceSet v := by ext e; induction e using Sym2.ind with | h a b => simp only [mem_edgeSet, incidenceSet, Set.mem_setOf_eq, Sym2.mem_iff] show (G.Adj a b ∧ (a = v ∨ b = v)) ↔ _ constructor · rintro ⟨h1, h2⟩; exact ⟨h1, h2.imp Eq.symm Eq.symm⟩ · rintro ⟨h1, h2⟩; exact ⟨h1, h2.imp Eq.symm Eq.symm⟩ have hScard : S.edgeSet.ncard = G.degree v := by rw [hSedge, ← coe_incidenceFinset, Set.ncard_coe_finset, card_incidenceFinset_eq_degree] -- matching let P : SimpleGraph V → Prop := fun H => H ≤ G ∧ ∀ x a b, H.Adj x a → H.Adj x b → a = b obtain ⟨M, hMmem, hMmax⟩ := Finset.exists_max_image (Finset.univ.filter P) (fun H => H.edgeSet.ncard) ⟨⊥, by simp [P]⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hMmem hMmax obtain ⟨hMG, hMmatch⟩ := hMmem have hMfree : (cycleGraph 4).Free M := by apply c4_free_of intro a b c d hab hbc hcd hda hac hbd exact hac (hMmatch b a c hab.symm hbc) have key : ∀ a b, G.Adj a b → (∃ x, M.Adj a x) ∨ (∃ x, M.Adj b x) := by intro a b hab by_contra hcon simp only [not_or, not_exists] at hcon obtain ⟨ha, hb⟩ := hcon let M' := M ⊔ SimpleGraph.edge a b have hP : P M' := by constructor · refine sup_le hMG ?_ intro x y hxy rw [edge_adj] at hxy rcases hxy.1 with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact hab · exact hab.symm · intro x c d hc hd simp only [M', sup_adj, edge_adj] at hc hd aesop have hlt : M.edgeSet.ncard < M'.edgeSet.ncard := by apply Set.ncard_lt_ncard _ (Set.toFinite _) rw [Set.ssubset_iff_of_subset (edgeSet_mono le_sup_left)] refine ⟨s(a, b), ?_, ?_⟩ · rw [mem_edgeSet]; simp [edge_adj, hab.ne] · rw [mem_edgeSet]; exact ha b have := hMmax M' hP omega let supp := Finset.univ.filter (fun x => ∃ y, M.Adj x y) have hsupp : supp.card ≤ 2 * M.edgeFinset.card := by rw [← M.sum_degrees_eq_twice_card_edges] calc supp.card = ∑ x ∈ supp, 1 := by simp _ ≤ ∑ x ∈ supp, M.degree x := Finset.sum_le_sum (fun x hx => by simp only [supp, Finset.mem_filter, Finset.mem_univ, true_and] at hx exact (M.degree_pos_iff_exists_adj x).2 hx) _ ≤ ∑ x, M.degree x := Finset.sum_le_sum_of_subset (Finset.subset_univ _) have hcount : G.edgeFinset.card ≤ 2 * M.edgeFinset.card * G.degree v := by have hsub : G.edgeFinset ⊆ supp.biUnion (fun x => G.incidenceFinset x) := by intro e he induction e using Sym2.ind with | h a b => rw [mem_edgeFinset, mem_edgeSet] at he rw [Finset.mem_biUnion] rcases key a b he with h | h · refine ⟨a, by simpa [supp] using h, ?_⟩ rw [mem_incidenceFinset]; exact ⟨he, by simp⟩ · refine ⟨b, by simpa [supp] using h, ?_⟩ rw [mem_incidenceFinset]; exact ⟨he, by simp⟩ calc G.edgeFinset.card ≤ ∑ x ∈ supp, (G.incidenceFinset x).card := (Finset.card_le_card hsub).trans Finset.card_biUnion_le _ ≤ ∑ x ∈ supp, G.degree v := Finset.sum_le_sum (fun x _ => by rw [card_incidenceFinset_eq_degree]; exact hv x) _ = supp.card * G.degree v := by simp _ ≤ 2 * M.edgeFinset.card * G.degree v := Nat.mul_le_mul_right _ hsupp have hGc : G.edgeSet.ncard = G.edgeFinset.card := by rw [← coe_edgeFinset, Set.ncard_coe_finset] have hMc : M.edgeSet.ncard = M.edgeFinset.card := by rw [← coe_edgeFinset, Set.ncard_coe_finset] by_cases hle : G.degree v ≤ M.edgeFinset.card · refine ⟨M, hMG, hMfree, ?_⟩ rw [hGc, hMc] apply real_aux calc G.edgeFinset.card ≤ 2 * M.edgeFinset.card * G.degree v := hcount _ ≤ 2 * M.edgeFinset.card * M.edgeFinset.card := Nat.mul_le_mul_left _ hle _ ≤ (2 * M.edgeFinset.card) ^ 2 := by nlinarith · refine ⟨S, hSG, hSfree, ?_⟩ rw [hGc, hScard] apply real_aux have hle' : M.edgeFinset.card ≤ G.degree v := by omega calc G.edgeFinset.card ≤ 2 * M.edgeFinset.card * G.degree v := hcount _ ≤ 2 * G.degree v * G.degree v := Nat.mul_le_mul_right _ (by omega) _ ≤ (2 * G.degree v) ^ 2 := by nlinarith