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.
In either case, this has been resolved by Li
[Li25]. In the first formulation, the transversal notion of criticality, Li proves that a $3$-critical $3$-uniform hypergraph must have a vertex of degree $\leq 6$.
On the other hand, in the second formulation, the chromatic notion of criticality, Li provides an explicit $3$-critical $3$-uniform hypergraph on $9$ vertices with minimum degree $7$.
View the LaTeX source
This page was last edited 01 January 2026. View history
Additional thanks to: Alfaiz and 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 2026-04-11
