/-! # Erdős problem 1068 — counterexample The construction below has chromatic cardinal aleph one and has no infinitely connected induced subgraph. The final theorem proves the counterexample target for the pinned Conjectures.io task. This file is the submission body. The verifier supplies the trusted imports and the enclosing `Bounty` namespace through its task header and footer. -/ noncomputable section open Set Cardinal Ordinal Function namespace Erdos1068Counterexample abbrev Level : Type := (Ordinal.omega 1).ToType abbrev Letter := Set ℕ abbrev Label := List Letter abbrev History := ℕ → Letter abbrev Node := Σ a : Level, Set.Iio a → Label abbrev Vertex := Node × History def levelZero : Level := Ordinal.ToType.mk ⟨0, (Cardinal.isSuccLimit_omega 1).pos⟩ def levelNext (a : Level) : Level := Ordinal.ToType.mk ⟨(a : Ordinal) + 1, (Cardinal.isSuccLimit_omega 1).add_one_lt a.toOrd.property⟩ lemma levelNext_gt (a : Level) : a < levelNext a := by apply (Ordinal.ToType.mk.symm.lt_iff_lt).mp simp only [levelNext, OrderIso.symm_apply_apply] exact lt_add_one (a : Ordinal) lemma level_bound (f : ℕ → Level) : ∃ a : Level, ∀ n, f n < a := by let o : Ordinal := ⨆ n, (f n : Ordinal) have ho : o < Ordinal.omega 1 := Ordinal.iSup_lt_omega_one (fun n => (f n).toOrd.property) refine ⟨Ordinal.ToType.mk ⟨o + 1, (Cardinal.isSuccLimit_omega 1).add_one_lt ho⟩, ?_⟩ intro n apply (Ordinal.ToType.mk.symm.lt_iff_lt).mp rw [OrderIso.symm_apply_apply] change (f n : Ordinal) < o + 1 exact (le_ciSup Ordinal.bddAbove_of_small n).trans_lt (lt_add_one o) lemma level_initial_countable (a : Level) : Countable (Set.Iio a) := by apply Cardinal.mk_le_aleph0_iff.mp apply Cardinal.lt_aleph_one_iff.mp simpa [Level] using Cardinal.mk_Iio_lt a (by simp [Level]) lemma mk_level : Cardinal.mk Level = Cardinal.aleph 1 := by simp [Level] lemma mk_letter : Cardinal.mk Letter = Cardinal.continuum := Cardinal.mk_set_nat lemma mk_label : Cardinal.mk Label = Cardinal.continuum := by rw [Cardinal.mk_list_eq_mk, mk_letter] lemma mk_history : Cardinal.mk History = Cardinal.continuum := by simp [History, Letter] def Prefix (t u : Node) : Prop := t.1 ≤ u.1 ∧ ∀ (a : Level) (ht : a < t.1) (hu : a < u.1), t.2 ⟨a, ht⟩ = u.2 ⟨a, hu⟩ lemma prefix_refl (t : Node) : Prefix t t := by exact ⟨le_rfl, fun _ _ _ => rfl⟩ lemma prefix_trans {t u v : Node} (htu : Prefix t u) (huv : Prefix u v) : Prefix t v := by refine ⟨htu.1.trans huv.1, ?_⟩ intro a ht hv exact (htu.2 a ht (ht.trans_le htu.1)).trans (huv.2 a (ht.trans_le htu.1) hv) lemma prefix_antisymm {t u : Node} (htu : Prefix t u) (hut : Prefix u t) : t = u := by obtain ⟨a, f⟩ := t obtain ⟨b, g⟩ := u have hab : a = b := le_antisymm htu.1 hut.1 subst b congr 1 funext i exact htu.2 i.1 i.2 i.2 lemma prefix_eq_of_height_eq {t u : Node} (htu : Prefix t u) (h : t.1 = u.1) : t = u := by apply prefix_antisymm htu refine ⟨h.ge, ?_⟩ intro a hu ht exact (htu.2 a ht hu).symm lemma prefixes_comparable {t u v : Node} (htv : Prefix t v) (huv : Prefix u v) : Prefix t u ∨ Prefix u t := by rcases le_total t.1 u.1 with h | h · left refine ⟨h, ?_⟩ intro a ht hu exact (htv.2 a ht (ht.trans_le htv.1)).trans (huv.2 a hu (hu.trans_le huv.1)).symm · right refine ⟨h, ?_⟩ intro a hu ht exact (huv.2 a hu (hu.trans_le huv.1)).trans (htv.2 a ht (ht.trans_le htv.1)).symm def Child (t : Node) (s : Label) (u : Node) : Prop := Prefix t u ∧ ∃ h : t.1 < u.1, u.2 ⟨t.1, h⟩ = s lemma child_height {t u : Node} {s : Label} (h : Child t s u) : t.1 < u.1 := h.2.choose lemma child_unique {t u : Node} {s r : Label} (hs : Child t s u) (hr : Child t r u) : s = r := hs.2.choose_spec.symm.trans hr.2.choose_spec lemma child_upwards {t u v : Node} {s : Label} (h : Child t s u) (huv : Prefix u v) : Child t s v := by refine ⟨prefix_trans h.1 huv, (child_height h).trans_le huv.1, ?_⟩ exact (huv.2 t.1 (child_height h) ((child_height h).trans_le huv.1)).symm.trans h.2.choose_spec lemma child_downwards {t u v : Node} {s : Label} (h : Child t s v) (htu : Prefix t u) (huv : Prefix u v) (hlt : t.1 < u.1) : Child t s u := by refine ⟨htu, hlt, ?_⟩ exact (huv.2 t.1 hlt (child_height h)).trans h.2.choose_spec def extendNode (t : Node) (s : Label) : Node := ⟨levelNext t.1, fun i => if h : i.1 < t.1 then t.2 ⟨i.1, h⟩ else s⟩ lemma extendNode_child (t : Node) (s : Label) : Child t s (extendNode t s) := by refine ⟨⟨(levelNext_gt t.1).le, ?_⟩, levelNext_gt t.1, ?_⟩ · intro a ht hu simp [extendNode, ht] · simp [extendNode] def historyPrefix (b : History) (n : ℕ) : Label := List.ofFn (fun i : Fin n => b i.1) lemma historyPrefix_length (b : History) (n : ℕ) : (historyPrefix b n).length = n := by simp [historyPrefix] lemma historyPrefix_length_eq {b c : History} {n m : ℕ} (h : historyPrefix b n = historyPrefix c m) : n = m := by simpa [historyPrefix_length] using congrArg List.length h lemma mk_node_le : Cardinal.mk Node ≤ Cardinal.continuum := by change Cardinal.mk (Σ a : Level, Set.Iio a → Label) ≤ Cardinal.continuum rw [Cardinal.mk_sigma] calc Cardinal.sum (fun a : Level => Cardinal.mk (Set.Iio a → Label)) ≤ Cardinal.sum (fun _ : Level => Cardinal.continuum) := by apply Cardinal.sum_le_sum intro a rw [Cardinal.mk_arrow, mk_label] simpa only [Cardinal.lift_id] using (Cardinal.power_le_power_left Cardinal.continuum_ne_zero (Cardinal.mk_le_aleph0_iff.mpr (level_initial_countable a))).trans_eq Cardinal.continuum_power_aleph0 _ = Cardinal.mk Level * Cardinal.continuum := Cardinal.sum_const' _ _ _ ≤ Cardinal.continuum * Cardinal.continuum := by apply mul_le_mul' · rw [mk_level] exact Cardinal.aleph_one_le_continuum · exact le_rfl _ = Cardinal.continuum := Cardinal.continuum_mul_self lemma mk_vertex_le : Cardinal.mk Vertex ≤ Cardinal.mk Letter := by rw [mk_letter] calc Cardinal.mk Vertex = Cardinal.mk Node * Cardinal.mk History := by simp [Vertex] _ ≤ Cardinal.continuum * Cardinal.continuum := mul_le_mul' mk_node_le mk_history.le _ = Cardinal.continuum := Cardinal.continuum_mul_self theorem vertex_cardinality : Cardinal.mk Vertex = Cardinal.continuum := by apply le_antisymm · simpa only [mk_letter] using mk_vertex_le · rw [← mk_history] exact Cardinal.mk_le_of_injective (f := fun b : History => ((⟨levelZero, fun _ => []⟩ : Node), b)) (fun _ _ h => congrArg Prod.snd h) def vertexCode : Vertex ↪ Letter := Classical.choice ((Cardinal.le_def Vertex Letter).mp mk_vertex_le) def targetPoint (t : Node) (s : Label) (a : Letter) : {v : Vertex // Child t s v.1} := by classical letI : Nonempty {v : Vertex // Child t s v.1} := ⟨⟨(extendNode t s, fun _ => ∅), extendNode_child t s⟩⟩ exact Function.invFun (fun v : {v : Vertex // Child t s v.1} => vertexCode v.1) a def target (t : Node) (s : Label) (a : Letter) : Vertex := (targetPoint t s a).1 lemma target_child (t : Node) (s : Label) (a : Letter) : Child t s (target t s a).1 := (targetPoint t s a).2 lemma target_hits (t : Node) (s : Label) (v : Vertex) (hv : Child t s v.1) : ∃ a, target t s a = v := by classical let _ : Nonempty {v : Vertex // Child t s v.1} := ⟨⟨(extendNode t s, fun _ => ∅), extendNode_child t s⟩⟩ refine ⟨vertexCode v, ?_⟩ change (Function.invFun (fun w : {v : Vertex // Child t s v.1} => vertexCode w.1) (vertexCode v)).1 = v have hi : Function.Injective (fun w : {v : Vertex // Child t s v.1} => vertexCode w.1) := vertexCode.injective.comp Subtype.val_injective exact congrArg Subtype.val (Function.leftInverse_invFun hi ⟨v, hv⟩) def Forward (u v : Vertex) : Prop := ∃ n : ℕ, v = target u.1 (historyPrefix u.2 n) (u.2 n) lemma forward_child {u v : Vertex} (h : Forward u v) : ∃ n, Child u.1 (historyPrefix u.2 n) v.1 := by obtain ⟨n, rfl⟩ := h exact ⟨n, target_child _ _ _⟩ lemma forward_height {u v : Vertex} (h : Forward u v) : u.1.1 < v.1.1 := by obtain ⟨n, hn⟩ := forward_child h exact child_height hn def graph : SimpleGraph Vertex where Adj u v := Forward u v ∨ Forward v u symm := ⟨fun _ _ h => Or.symm h⟩ loopless := ⟨by intro u h exact lt_irrefl u.1.1 (forward_height (h.elim id id))⟩ lemma adjacent_comparable {u v : Vertex} (h : graph.Adj u v) : Prefix u.1 v.1 ∨ Prefix v.1 u.1 := by rcases h with h | h · exact Or.inl (forward_child h).choose_spec.1 · exact Or.inr (forward_child h).choose_spec.1 lemma adjacent_different_heights {u v : Vertex} (h : graph.Adj u v) : u.1.1 ≠ v.1.1 := by rcases h with h | h · exact (forward_height h).ne · exact (forward_height h).ne' lemma adjacent_forward_of_height {u v : Vertex} (h : graph.Adj u v) (huv : u.1.1 < v.1.1) : Forward u v := by rcases h with h | h · exact h · exact False.elim (lt_asymm huv (forward_height h)) def chainLabel (t : ℕ → Node) (a : Level) : Label := by classical exact if h : ∃ n, a < (t n).1 then (t h.choose).2 ⟨a, h.choose_spec⟩ else [] lemma chainLabel_eq (t : ℕ → Node) (ht : ∀ n m, n ≤ m → Prefix (t n) (t m)) (n : ℕ) (a : Level) (ha : a < (t n).1) : chainLabel t a = (t n).2 ⟨a, ha⟩ := by classical have hex : ∃ m, a < (t m).1 := ⟨n, ha⟩ dsimp [chainLabel] rw [dite_eq_left hex] rcases le_total hex.choose n with h | h · exact (ht hex.choose n h).2 a hex.choose_spec ha · exact ((ht n hex.choose h).2 a ha hex.choose_spec).symm def chainUpper (t : ℕ → Node) : Node := ⟨(level_bound (fun n => (t n).1)).choose, fun a => chainLabel t a.1⟩ lemma prefix_chainUpper (t : ℕ → Node) (ht : ∀ n m, n ≤ m → Prefix (t n) (t m)) (n : ℕ) : Prefix (t n) (chainUpper t) := by refine ⟨((level_bound (fun n => (t n).1)).choose_spec n).le, ?_⟩ intro a ha hb exact (chainLabel_eq t ht n a ha).symm def Drops (c : Vertex → ℕ) (k : ℕ) (t : Node) : Prop := ∀ v : Vertex, Prefix t v.1 → c v ≠ k def trimColor (c : Vertex → ℕ) (k : ℕ) (t : Node) : Node := by classical exact if h : ∃ u, Prefix t u ∧ Drops c k u then h.choose else t lemma trimColor_extends (c : Vertex → ℕ) (k : ℕ) (t : Node) : Prefix t (trimColor c k t) := by classical unfold trimColor split · exact Exists.choose_spec ‹∃ u, Prefix t u ∧ Drops c k u› |>.1 · exact prefix_refl t lemma trimColor_drops (c : Vertex → ℕ) (k : ℕ) (t : Node) (h : ∃ u, Prefix t u ∧ Drops c k u) : Drops c k (trimColor c k t) := by classical unfold trimColor rw [dite_eq_left h] exact h.choose_spec.2 def paletteChain (c : Vertex → ℕ) : ℕ → Node | 0 => ⟨levelZero, fun _ => []⟩ | n + 1 => trimColor c n (paletteChain c n) lemma paletteChain_increasing (c : Vertex → ℕ) (n m : ℕ) (h : n ≤ m) : Prefix (paletteChain c n) (paletteChain c m) := by induction m, h using Nat.le_induction with | base => exact prefix_refl _ | succ m hm ih => exact prefix_trans ih (trimColor_extends c m _) def StablePalette (c : Vertex → ℕ) (t : Node) : Prop := ∀ u : Node, Prefix t u → ∀ k : ℕ, (∃ v : Vertex, Prefix t v.1 ∧ c v = k) → ∃ v : Vertex, Prefix u v.1 ∧ c v = k lemma exists_stablePalette (c : Vertex → ℕ) : ∃ t : Node, StablePalette c t := by classical let t := chainUpper (paletteChain c) have ht (n : ℕ) : Prefix (paletteChain c n) t := prefix_chainUpper _ (paletteChain_increasing c) n refine ⟨t, ?_⟩ intro u htu k hk have hnot : ¬ ∃ w, Prefix (paletteChain c k) w ∧ Drops c k w := by intro hex obtain ⟨v, htv, hcv⟩ := hk have hd : Drops c k (paletteChain c (k + 1)) := trimColor_drops c k _ hex exact hd v (prefix_trans (ht (k + 1)) htv) hcv by_contra hmissing apply hnot refine ⟨u, prefix_trans (ht k) htu, ?_⟩ intro v huv hcv exact hmissing ⟨v, huv, hcv⟩ lemma stablePalette_child_color (c : Vertex → ℕ) (t : Node) (ht : StablePalette c t) (s : Label) (k : ℕ) (hk : ∃ v : Vertex, Prefix t v.1 ∧ c v = k) : ∃ a : Letter, c (target t s a) = k := by obtain ⟨v, hv, hcv⟩ := ht (extendNode t s) (extendNode_child t s).1 k hk obtain ⟨a, ha⟩ := target_hits t s v (child_upwards (extendNode_child t s) hv) exact ⟨a, ha ▸ hcv⟩ def paletteSchedule (c : Vertex → ℕ) (t : Node) (n : ℕ) : ℕ := by classical exact if ∃ v : Vertex, Prefix t v.1 ∧ c v = n then n else c (t, fun _ => ∅) lemma paletteSchedule_present (c : Vertex → ℕ) (t : Node) (n : ℕ) : ∃ v : Vertex, Prefix t v.1 ∧ c v = paletteSchedule c t n := by classical unfold paletteSchedule split · exact ‹∃ v : Vertex, Prefix t v.1 ∧ c v = n› · exact ⟨(t, fun _ => ∅), prefix_refl t, rfl⟩ def diagonalHistory (select : Label → Letter) : ℕ → Letter := WellFounded.fix (wellFounded_lt : WellFounded ((· < ·) : ℕ → ℕ → Prop)) (fun n previous => select (List.ofFn fun i : Fin n => previous i.1 i.2)) lemma diagonalHistory_eq (select : Label → Letter) (n : ℕ) : diagonalHistory select n = select (historyPrefix (diagonalHistory select) n) := by rw [diagonalHistory, WellFounded.fix_eq] rfl lemma every_nat_coloring_conflict (c : Vertex → ℕ) : ∃ u v : Vertex, graph.Adj u v ∧ c u = c v := by classical obtain ⟨t, ht⟩ := exists_stablePalette c have possible (s : Label) : ∃ a : Letter, c (target t s a) = paletteSchedule c t s.length := stablePalette_child_color c t ht s _ (paletteSchedule_present c t _) let select : Label → Letter := fun s => (possible s).choose let b : History := diagonalHistory select let u : Vertex := (t, b) let k : ℕ := c u let v : Vertex := target t (historyPrefix b k) (b k) have hk : ∃ w : Vertex, Prefix t w.1 ∧ c w = k := ⟨u, prefix_refl t, rfl⟩ have hb : b k = select (historyPrefix b k) := diagonalHistory_eq select k have hv : c v = k := by change c (target t (historyPrefix b k) (b k)) = k rw [hb] have h : c (target t (historyPrefix b k) (select (historyPrefix b k))) = paletteSchedule c t (historyPrefix b k).length := (possible (historyPrefix b k)).choose_spec have hschedule : paletteSchedule c t (historyPrefix b k).length = k := by rw [historyPrefix_length] simp [paletteSchedule, hk] exact h.trans hschedule exact ⟨u, v, Or.inl ⟨k, rfl⟩, hv.symm⟩ def Agree (b c : History) (k : ℕ) : Prop := ∀ i, i < k → b i = c i lemma agree_refl (b : History) (k : ℕ) : Agree b b k := fun _ _ => rfl lemma agree_mono {b c : History} {k n : ℕ} (h : Agree b c k) (hn : n ≤ k) : Agree b c n := fun i hi => h i (hi.trans_le hn) lemma agree_trans {b c d : History} {k : ℕ} (hbc : Agree b c k) (hcd : Agree c d k) : Agree b d k := fun i hi => (hbc i hi).trans (hcd i hi) lemma historyPrefix_eq_of_agree {b c : History} {k : ℕ} (h : Agree b c k) : historyPrefix b k = historyPrefix c k := by apply congrArg List.ofFn funext i exact h i.1 i.2 lemma agree_of_historyPrefix_eq {b c : History} {k : ℕ} (h : historyPrefix b k = historyPrefix c k) : Agree b c k := by intro i hi exact congrFun (List.ofFn_injective h) ⟨i, hi⟩ def Inside (t : Node) (b : History) (k : ℕ) (v : Vertex) : Prop := (v.1 = t ∧ Agree v.2 b k) ∨ ∃ c : History, ∃ n : ℕ, k ≤ n ∧ Agree c b k ∧ Child t (historyPrefix c n) v.1 def Frontier (t : Node) (b : History) (k : ℕ) : Set Vertex := Set.range (fun i : Fin k => target t (historyPrefix b i.1) (b i.1)) lemma frontier_finite (t : Node) (b : History) (k : ℕ) : (Frontier t b k).Finite := Set.finite_range _ lemma frontier_misses_bag (t : Node) (b : History) (k : ℕ) (v : Vertex) (hv : v.1 = t) : v ∉ Frontier t b k := by rintro ⟨i, hi⟩ change target t (historyPrefix b i.1) (b i.1) = v at hi have h := child_height (target_child t (historyPrefix b i.1) (b i.1)) rw [hi, hv] at h exact lt_irrefl _ h lemma inside_base (t : Node) (b : History) (k : ℕ) : Inside t b k (t, b) := Or.inl ⟨rfl, agree_refl b k⟩ lemma not_inside_bag {t : Node} {b c : History} {k : ℕ} (h : ¬ Agree c b k) : ¬ Inside t b k (t, c) := by rintro (⟨_, hc⟩ | ⟨d, n, _, _, hd⟩) · exact h hc · exact lt_irrefl _ (child_height hd) lemma inside_boundary {t : Node} {b : History} {k : ℕ} {u v : Vertex} (hu : Inside t b k u) (hv : Prefix t v.1) (hadj : graph.Adj u v) : Inside t b k v ∨ v ∈ Frontier t b k := by classical rcases hadj with hforward | hbackward · obtain ⟨n, rfl⟩ := hforward rcases hu with ⟨hnode, hagree⟩ | ⟨c, m, hkm, hagree, hc⟩ · by_cases hn : n < k · right have hp := historyPrefix_eq_of_agree (agree_mono hagree hn.le) have ha := hagree n hn change target u.1 (historyPrefix u.2 n) (u.2 n) ∈ Frontier t b k rw [hnode, hp, ha] exact ⟨⟨n, hn⟩, rfl⟩ · left right refine ⟨u.2, n, Nat.le_of_not_gt hn, hagree, ?_⟩ simpa [hnode] using target_child u.1 (historyPrefix u.2 n) (u.2 n) · left right exact ⟨c, m, hkm, hagree, child_upwards hc (target_child u.1 (historyPrefix u.2 n) (u.2 n)).1⟩ · obtain ⟨n, hn⟩ := hbackward have hvu : Child v.1 (historyPrefix v.2 n) u.1 := by rw [hn] exact target_child _ _ _ rcases hu with ⟨hnode, _⟩ | ⟨c, m, hkm, hagree, hc⟩ · have hlt := child_height hvu rw [hnode] at hlt exact False.elim ((not_lt_of_ge hv.1) hlt) · by_cases hnode : v.1 = t · have hlabels : historyPrefix v.2 n = historyPrefix c m := by apply child_unique (t := t) (u := u.1) · simpa [hnode] using hvu · exact hc have hnm := historyPrefix_length_eq hlabels subst m left left exact ⟨hnode, agree_trans (agree_mono (agree_of_historyPrefix_eq hlabels) hkm) hagree⟩ · have hlt : t.1 < v.1.1 := by apply lt_of_le_of_ne hv.1 intro hlevels exact hnode (prefix_eq_of_height_eq hv hlevels).symm left right exact ⟨c, m, hkm, hagree, child_downwards hc hv hvu.1 hlt⟩ lemma walk_preserves_on {α : Type*} {G : SimpleGraph α} {S P : α → Prop} (hstep : ∀ a b, S a → S b → G.Adj a b → P a → P b) {a b : α} (p : G.Walk a b) (hs : ∀ x ∈ p.support, S x) (ha : P a) : P b := by induction p with | nil => exact ha | @cons a c b hac p ih => apply ih · intro x hx exact hs x (by simp [SimpleGraph.Walk.support_cons, hx]) · exact hstep a c (hs a (by simp [SimpleGraph.Walk.support_cons])) (hs c (by simp [SimpleGraph.Walk.support_cons])) hac ha lemma mem_support_dropLast {α : Type*} {G : SimpleGraph α} {v : α} : ∀ {w : α} (q : G.Walk w v) {x : α}, x ∈ q.support → x ≠ v → x ∈ q.support.dropLast := by intro w q induction q with | nil => intro x hx hxv rw [SimpleGraph.Walk.support_nil] at hx exact absurd (List.mem_singleton.mp hx) hxv | cons _ r ih => intro x hx hxv rw [SimpleGraph.Walk.support_cons] at hx ⊢ rw [List.dropLast_cons_of_ne_nil r.support_ne_nil] rcases List.mem_cons.mp hx with h1 | h1 · exact List.mem_cons.mpr (Or.inl h1) · exact List.mem_cons.mpr (Or.inr (ih h1 hxv)) lemma mem_interior {α : Type*} {G : SimpleGraph α} {u v x : α} (p : G.Walk u v) (hx : x ∈ p.support) (hxu : x ≠ u) (hxv : x ≠ v) : x ∈ p.support.tail.dropLast := by rw [← SimpleGraph.Walk.cons_tail_support p] at hx rcases List.mem_cons.mp hx with h1 | h1 · exact absurd h1 hxu · cases p with | nil => simp at h1 | cons _ q => rw [SimpleGraph.Walk.support_cons] at h1 rw [SimpleGraph.Walk.support_cons] simpa using mem_support_dropLast q (by simpa using h1) hxv lemma infinite_connected_avoids {α : Type*} {G : SimpleGraph α} (hG : G.InfinitelyConnected) {u v : α} (huv : u ≠ v) (S : Set α) (hS : S.Finite) (hu : u ∉ S) (hv : v ∉ S) : ∃ p : G.Walk u v, ∀ x ∈ p.support, x ∉ S := by classical obtain ⟨P, hP, _, hdisjoint⟩ := @hG.2 u v huv let badAt (x : α) : Set (G.Walk u v) := {p | p ∈ P ∧ x ∈ p.support.tail.dropLast} have hbadAt (x : α) : (badAt x).Finite := by apply Set.Subsingleton.finite intro p hp q hq by_contra hpq exact List.disjoint_left.mp (hdisjoint hp.1 hq.1 hpq) hp.2 hq.2 have hbad : (⋃ x ∈ S, badAt x).Finite := hS.biUnion (fun x _ => hbadAt x) obtain ⟨p, hp, hgood⟩ := hP.exists_notMem_finite hbad refine ⟨p, ?_⟩ intro x hx hxs apply hgood apply Set.mem_iUnion.mpr refine ⟨x, Set.mem_iUnion.mpr ⟨hxs, ?_⟩⟩ exact ⟨hp, mem_interior p hx (fun h => hu (h ▸ hxs)) (fun h => hv (h ▸ hxs))⟩ lemma infinite_connected_connected {α : Type*} {G : SimpleGraph α} (hG : G.InfinitelyConnected) : G.Connected := by classical let _ : Nontrivial α := hG.1 rw [SimpleGraph.connected_iff] refine ⟨fun u v => ?_, inferInstance⟩ rcases eq_or_ne u v with rfl | huv · exact SimpleGraph.Reachable.refl u · obtain ⟨P, hP, _, _⟩ := @hG.2 u v huv obtain ⟨p, _⟩ := hP.nonempty exact ⟨p⟩ lemma infinite_connected_infinite {α : Type*} {G : SimpleGraph α} (hG : G.InfinitelyConnected) : Infinite α := by classical rcases finite_or_infinite α with hfinite | hinfinite · let _ : Finite α := hfinite let _ : Fintype α := Fintype.ofFinite α let _ : Nontrivial α := hG.1 obtain ⟨u, v, huv⟩ := exists_pair_ne α obtain ⟨P, hP, hp, _⟩ := @hG.2 u v huv have hfinitePaths : {p : G.Walk u v | p.IsPath}.Finite := Set.finite_def.mpr ⟨SimpleGraph.Path.instFintype G⟩ exact False.elim (hP (hfinitePaths.subset hp)) · exact hinfinite lemma infinite_connected_neighbors {α : Type*} {G : SimpleGraph α} (hG : G.InfinitelyConnected) (u : α) : (G.neighborSet u).Infinite := by classical let _ : Infinite α := infinite_connected_infinite hG intro hfinite obtain ⟨v, hv⟩ := (hfinite.insert u).exists_notMem have hvprops : v ≠ u ∧ v ∉ G.neighborSet u := by simpa only [Set.mem_insert_iff, not_or] using hv have hvu : v ≠ u := hvprops.1 obtain ⟨p, hp⟩ := infinite_connected_avoids hG hvu.symm (G.neighborSet u) hfinite (by simp) hvprops.2 cases p with | nil => exact hvu rfl | @cons a b c hab p => exact hp b (by simp [SimpleGraph.Walk.support_cons]) hab lemma adjacent_preserves_cone {t : Node} {u v : Vertex} (htu : Prefix t u.1) (hmin : t.1 ≤ v.1.1) (hadj : graph.Adj u v) : Prefix t v.1 := by rcases adjacent_comparable hadj with huv | hvu · exact prefix_trans htu huv · rcases prefixes_comparable htu hvu with htv | hvt · exact htv · have heq : v.1 = t := prefix_eq_of_height_eq hvt (le_antisymm hvt.1 hmin) simpa [heq] using prefix_refl t lemma adjacent_preserves_child {t : Node} {s : Label} {u v : Vertex} (hu : Child t s u.1) (hv : Prefix t v.1) (hne : v.1 ≠ t) (hadj : graph.Adj u v) : Child t s v.1 := by rcases hadj with hforward | hbackward · exact child_upwards hu (forward_child hforward).choose_spec.1 · apply child_downwards hu hv (forward_child hbackward).choose_spec.1 by_contra h have heq : t = v.1 := prefix_eq_of_height_eq hv (le_antisymm hv.1 (not_lt.mp h)) exact hne heq.symm lemma forward_same_child_unique {r u v : Vertex} {s : Label} (hru : Forward r u) (hrv : Forward r v) (hu : Child r.1 s u.1) (hv : Child r.1 s v.1) : u = v := by obtain ⟨n, hn⟩ := hru obtain ⟨m, hm⟩ := hrv have hlabeln : historyPrefix r.2 n = s := by apply child_unique _ hu rw [hn] exact target_child _ _ _ have hlabelm : historyPrefix r.2 m = s := by apply child_unique _ hv rw [hm] exact target_child _ _ _ have hnm : n = m := historyPrefix_length_eq (hlabeln.trans hlabelm.symm) subst m exact hn.trans hm.symm theorem no_infinitelyConnected_induce (W : Set Vertex) : ¬ (graph.induce W).InfinitelyConnected := by classical intro hG let _ : Nontrivial W := hG.1 obtain ⟨a, ha, hminimal⟩ := (wellFounded_lt : WellFounded ((· < ·) : Level → Level → Prop)).has_min (Set.range (fun v : W => v.1.1.1)) (Set.range_nonempty _) obtain ⟨r, rfl⟩ := ha let t : Node := r.1.1 have hmin (v : W) : t.1 ≤ v.1.1.1 := le_of_not_gt (hminimal _ ⟨v, rfl⟩) have hcone (v : W) : Prefix t v.1.1 := by obtain ⟨p⟩ := (infinite_connected_connected hG) r v exact walk_preserves_on (S := fun _ : W => True) (P := fun w : W => Prefix t w.1.1) (fun _ y _ _ hadj hx => adjacent_preserves_cone hx (hmin y) hadj) p (fun _ _ => trivial) (prefix_refl t) have hbag (w : W) (hw : w.1.1 = t) : w = r := by by_contra hne have hhist : w.1.2 ≠ r.1.2 := by intro h apply hne apply Subtype.ext exact Prod.ext hw h obtain ⟨n, hn⟩ : ∃ n, w.1.2 n ≠ r.1.2 n := by by_contra h push Not at h exact hhist (funext h) have hnotAgree : ¬ Agree w.1.2 r.1.2 (n + 1) := fun hagree => hn (hagree n (Nat.lt_succ_self n)) let F : Set Vertex := Frontier t r.1.2 (n + 1) let S : Set W := {x | x.1 ∈ F} have hS : S.Finite := (frontier_finite t r.1.2 (n + 1)).preimage Subtype.val_injective.injOn have hrS : r ∉ S := frontier_misses_bag t r.1.2 (n + 1) r.1 rfl have hwS : w ∉ S := frontier_misses_bag t r.1.2 (n + 1) w.1 hw obtain ⟨p, hp⟩ := infinite_connected_avoids hG (Ne.symm hne) S hS hrS hwS have hinside : Inside t r.1.2 (n + 1) w.1 := by apply walk_preserves_on (S := fun x : W => x.1 ∉ F) (P := fun x : W => Inside t r.1.2 (n + 1) x.1) (fun x y _ hy hadj hx => (inside_boundary hx (hcone y) hadj).resolve_right hy) p hp (inside_base t r.1.2 (n + 1)) rcases hinside with ⟨_, hagree⟩ | ⟨c, m, _, _, hc⟩ · exact hnotAgree hagree · have hlt := child_height hc rw [hw] at hlt exact lt_irrefl t.1 hlt obtain ⟨u, hu, v, hv, huv⟩ := (infinite_connected_neighbors hG r).nontrivial have hforward (w : W) (hw : (graph.induce W).Adj r w) : Forward r.1 w.1 := by change Forward r.1 w.1 ∨ Forward w.1 r.1 at hw rcases hw with h | h · exact h · exact False.elim ((not_lt_of_ge (hmin w)) (forward_height h)) obtain ⟨n, hchild⟩ := forward_child (hforward u hu) have hru : r ≠ u := (graph.induce W).ne_of_adj hu have hrv : r ≠ v := (graph.induce W).ne_of_adj hv obtain ⟨p, hp⟩ := infinite_connected_avoids hG huv {r} (Set.finite_singleton r) (fun h => hru (Set.mem_singleton_iff.mp h).symm) (fun h => hrv (Set.mem_singleton_iff.mp h).symm) have hchildv : Child t (historyPrefix r.1.2 n) v.1.1 := by apply walk_preserves_on (S := fun x : W => x ≠ r) (P := fun x : W => Child t (historyPrefix r.1.2 n) x.1.1) (fun x y _ hy hadj hx => adjacent_preserves_child hx (hcone y) (fun hyt => hy (hbag y hyt)) hadj) p (fun x hx hxr => hp x hx (by simp [hxr])) hchild exact huv (Subtype.ext (forward_same_child_unique (hforward u hu) (hforward v hv) hchild hchildv)) theorem chromaticCardinal_eq : graph.chromaticCardinal = Cardinal.aleph 1 := by classical have hupper : graph.chromaticCardinal ≤ Cardinal.aleph 1 := by rw [← mk_level] apply csInf_le (OrderBot.bddBelow _) refine ⟨Level, rfl, ?_⟩ exact ⟨SimpleGraph.Coloring.mk (fun v : Vertex => v.1.1) (fun h => adjacent_different_heights h)⟩ have hlower : ¬ graph.chromaticCardinal ≤ Cardinal.aleph0 := by intro h have hnonempty : {κ : Cardinal | ∃ (C : Type) (_ : Cardinal.mk C = κ), Nonempty (graph.Coloring C)}.Nonempty := ⟨Cardinal.mk Vertex, Vertex, rfl, ⟨graph.selfColoring⟩⟩ obtain ⟨C, hC, hcolor⟩ := csInf_mem hnonempty have hsmall : Cardinal.mk C ≤ Cardinal.aleph0 := hC.trans_le h let _ : Countable C := Cardinal.mk_le_aleph0_iff.mp hsmall obtain ⟨f, hf⟩ := Countable.exists_injective_nat C obtain ⟨color⟩ := hcolor let coloring : graph.Coloring ℕ := graph.recolorOfEmbedding ⟨f, hf⟩ color obtain ⟨u, v, huv, heq⟩ := every_nat_coloring_conflict coloring exact coloring.valid huv heq exact le_antisymm hupper (Cardinal.aleph_one_le_iff.mpr (lt_of_not_ge hlower)) end Erdos1068Counterexample theorem target : ¬ (fcTypeOfName% "Erdos1068.erdos_1068") := by intro h obtain ⟨s, _, hs⟩ := h.mp trivial Erdos1068Counterexample.Vertex Erdos1068Counterexample.graph Erdos1068Counterexample.chromaticCardinal_eq exact Erdos1068Counterexample.no_infinitelyConnected_induce s hs end