/-
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 1032
References:
[Er93] Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333-350.
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).
[Di52] Dirac, G. A., A property of $4$-chromatic graphs and some remarks on critical graphs. J. London Math. Soc. 27 (1952), 85-92.
[Si72] Simonovits, M., On colour-critical graphs. Studia Sci. Math. Hungar. 7 (1972), 67-81.
[To72] Toft, B., Two theorems on critical $4$-chromatic graphs. Studia Sci. Math. Hungar. 7 (1972), 83-89.
[Ma15] Markström, K. (ed.), Problem collection from the IML programme: Graphs, Hypergraphs, and Computing. arXiv:1511.00270 (2015). Problem 5.1 (M. Simonovits).
See also erdosproblems.com/917 and erdosproblems.com/944.
@[expose] public sectionopen Filternamespace Erdos1032
A graph G is k-critical if it has chromatic number k and every proper subgraph has
chromatic number less than k. For a finite graph a proper subgraph misses a vertex or an edge, so
this holds iff G.IsCritical k (deleting any vertex lowers the chromatic number) and deleting any
edge lowers the chromatic number.
The definition on the problem page uses only the edge condition. This would allow isolated vertices, but a minimum degree $\geq cn$ with $c > 0$ excludes them, so the two notions agree in the statements below.
def IsKCritical {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop :=
G.IsCritical k ∧ ∀ e ∈ G.edgeSet, G.IsCriticalEdge eopen scoped Classical inWe say that a graph is $4$-chromatic critical if it has chromatic number $4$, and removing any edge decreases the chromatic number to $3$.
Is there, for arbitrarily large $n$, a $4$-chromatic critical graph on $n$ vertices with minimum degree $\gg n$?
This is a question of Erdős [Er93, p. 341] (see also [Va99, 3.60]). We read $\gg n$ as $\geq cn$ for a fixed constant $c > 0$.
@[category research open, question, AMS 5]
theorem erdos_1032 :
∃ c : ℝ, 0 < c ∧ ∃ᶠ n : ℕ in atTop,
∃ G : SimpleGraph (Fin n), IsKCritical G 4 ∧ c * (n : ℝ) ≤ (G.minDegree : ℝ) := ⊢ ∃ c, 0 < c ∧ ∃ᶠ (n : ℕ) in atTop, ∃ G, IsKCritical G 4 ∧ c * ↑n ≤ ↑G.minDegree
All goals completed! 🐙open scoped Classical inIs there, for arbitrarily large $n$, a $5$-chromatic critical graph on $n$ vertices with minimum degree $\gg n$?
This problem is also open for $5$-chromatic critical graphs.
@[category research open, question, AMS 5]
theorem erdos_1032.variants.five :
∃ c : ℝ, 0 < c ∧ ∃ᶠ n : ℕ in atTop,
∃ G : SimpleGraph (Fin n), IsKCritical G 5 ∧ c * (n : ℝ) ≤ (G.minDegree : ℝ) := ⊢ ∃ c, 0 < c ∧ ∃ᶠ (n : ℕ) in atTop, ∃ G, IsKCritical G 5 ∧ c * ↑n ≤ ↑G.minDegree
All goals completed! 🐙open scoped Classical inDirac gave an example of a $6$-chromatic critical graph with minimum degree $>n/2$.
Dirac's graphs join two disjoint odd cycles of length $n/2$ [Di52], [Ma15]. Here we state that there are such graphs for infinitely many $n$.
@[category research solved, AMS 5]
theorem erdos_1032.variants.dirac_six :
∃ᶠ n : ℕ in atTop,
∃ G : SimpleGraph (Fin n), IsKCritical G 6 ∧ (n : ℝ) / 2 < (G.minDegree : ℝ) := ⊢ ∃ᶠ (n : ℕ) in atTop, ∃ G, IsKCritical G 6 ∧ ↑n / 2 < ↑G.minDegree
All goals completed! 🐙open scoped Classical inSimonovits [Si72] and Toft [To72] independently constructed $4$-chromatic critical graphs with minimum degree $\gg n^{1/3}$.
We state this as in [Ma15, Problem 5.1]: there are $4$-critical graphs on $n$ vertices with minimum degree at least $c n^{1/3}$ for infinitely many $n$, for a fixed constant $c > 0$.
@[category research solved, AMS 5]
theorem erdos_1032.variants.simonovits_toft :
∃ c : ℝ, 0 < c ∧ ∃ᶠ n : ℕ in atTop,
∃ G : SimpleGraph (Fin n),
IsKCritical G 4 ∧ c * (n : ℝ) ^ ((1 : ℝ) / 3) ≤ (G.minDegree : ℝ) := ⊢ ∃ c, 0 < c ∧ ∃ᶠ (n : ℕ) in atTop, ∃ G, IsKCritical G 4 ∧ c * ↑n ^ (1 / 3) ≤ ↑G.minDegree
All goals completed! 🐙end Erdos1032