Problem Statement
Does there exist a $3$-critical $3$-uniform hypergraph in which every vertex has degree $\geq 7$?
Categories:
Graph Theory Hypergraphs
Progress
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$.
Source: erdosproblems.com/834 | Last verified: January 16, 2026