/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 1174
References:
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999), problem 7.91.
@[expose] public sectionopen Cardinalopen scoped Cardinalnamespace Erdos1174Erdős Problem 1174, part (i) [Va99, 7.91]. A problem of Erdős and Hajnal: does there exist a graph $G$ with no $K_4$ such that every edge colouring of $G$ with countably many colours contains a monochromatic $K_3$?
For simplicity the colourings are given on all unordered pairs $\operatorname{Sym}_2(V)$; only the values on the edges of $G$ matter, since a monochromatic triangle is witnessed by edges alone.
Shelah proved that a graph with this property can consistently exist, so the problem is not disprovable in ZFC; whether such a graph exists outright remains open.
@[category research open, question, AMS 3 5]
theorem erdos_1174.parts.i :
∃ (V : Type) (G : SimpleGraph V), G.CliqueFree 4 ∧
∀ c : Sym2 V → ℕ, ∃ x y z : V,
G.Adj x y ∧ G.Adj y z ∧ G.Adj x z ∧
c s(x, y) = c s(y, z) ∧ c s(y, z) = c s(x, z) := ⊢ ∃ V G,
G.CliqueFree 4 ∧
∀ (c : Sym2 V → ℕ), ∃ x y z, G.Adj x y ∧ G.Adj y z ∧ G.Adj x z ∧ c s(x, y) = c s(y, z) ∧ c s(y, z) = c s(x, z)
All goals completed! 🐙Erdős Problem 1174, part (ii) [Va99, 7.91]. A problem of Erdős and Hajnal: does there exist a graph $G$ with no $K_{\aleph_1}$ (that is, every clique of $G$ is countable) such that every edge colouring of $G$ with countably many colours contains a monochromatic $K_{\aleph_0}$ (an infinite clique all of whose edges receive the same colour)?
For simplicity the colourings are given on all unordered pairs $\operatorname{Sym}_2(V)$; only the values on the edges of $G$ matter.
Shelah proved that a graph with this property can consistently exist, so the problem is not disprovable in ZFC; whether such a graph exists outright remains open.
@[category research open, question, AMS 3 5]
theorem erdos_1174.parts.ii :
∃ (V : Type) (G : SimpleGraph V),
(∀ S : Set V, G.IsClique S → #S ≤ ℵ₀) ∧
∀ c : Sym2 V → ℕ, ∃ S : Set V, G.IsClique S ∧ S.Infinite ∧
∃ k : ℕ, ∀ x ∈ S, ∀ y ∈ S, x ≠ y → c s(x, y) = k := ⊢ ∃ V G,
(∀ (S : Set V), G.IsClique S → #↑S ≤ ℵ₀) ∧
∀ (c : Sym2 V → ℕ), ∃ S, G.IsClique S ∧ S.Infinite ∧ ∃ k, ∀ x ∈ S, ∀ y ∈ S, x ≠ y → c s(x, y) = k
All goals completed! 🐙The complete graph on $\mathbb{N}$ is not $K_4$-free, so it is not a candidate for part (i).
@[category test, AMS 5]
theorem top_not_cliqueFree_four : ¬ (⊤ : SimpleGraph ℕ).CliqueFree 4 :=
SimpleGraph.IsContained.not_cliqueFree
⟨SimpleGraph.Embedding.toCopy (⟨Fin.valEmbedding, ⊢ ∀ {a b : Fin 4}, ⊤.Adj (Fin.valEmbedding a) (Fin.valEmbedding b) ↔ (SimpleGraph.completeGraph (Fin 4)).Adj a b All goals completed! 🐙⟩ :
SimpleGraph.completeGraph (Fin 4) ↪g (⊤ : SimpleGraph ℕ))⟩The empty graph on $\mathbb{N}$ is trivially $K_4$-free but fails the colouring property of part (i): it has no triangles at all, so the $K_4$-free condition alone is not enough.
@[category test, AMS 5]
theorem bot_fails_colouring_property :
¬ ∀ c : Sym2 ℕ → ℕ, ∃ x y z : ℕ,
(⊥ : SimpleGraph ℕ).Adj x y ∧ (⊥ : SimpleGraph ℕ).Adj y z ∧
(⊥ : SimpleGraph ℕ).Adj x z ∧
c s(x, y) = c s(y, z) ∧ c s(y, z) = c s(x, z) := ⊢ ¬∀ (c : Sym2 ℕ → ℕ), ∃ x y z, ⊥.Adj x y ∧ ⊥.Adj y z ∧ ⊥.Adj x z ∧ c s(x, y) = c s(y, z) ∧ c s(y, z) = c s(x, z)
All goals completed! 🐙end Erdos1174