VERIFIABLE
Open, but could be proved with a finite example.
Does there exist a $3$-critical $3$-uniform hypergraph in which every vertex has degree $\geq 7$?
A problem of Erdős and Lovász.
They do not specify what is meant by $3$-critical. One definition in the literature is: a hypergraph is $3$-critical if there is a set of $3$ vertices which intersects every edge, but no such set of size $2$, and yet for any edge $e$ there is a pair of vertices which intersects every edge except $e$. Raphael Steiner observes that a $3$-critical hypergraph in this sense has bounded size, so this problem would be a finite computation, and perhaps is not what they meant.
An alternative definition is that a hypergraph is $3$-critical if it has chromatic number $3$, but its chromatic number becomes $2$ after deleting any edge or vertex.
View the LaTeX source
Additional thanks to: Raphael Steiner
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #834, https://www.erdosproblems.com/834, accessed 2025-11-15
