Erdős Problem #1032 — We say that a graph is $4$-chromatic critical if it has chromatic number $4$, and removing any edge decreases the chromatic number to $3$.

The problem asks whether arbitrarily large edge-critical graphs requiring four colours can have minimum degree proportional to their number of vertices. Erdős reportedly posed it more than twenty years before the historical record.

Known results

• Simonovits and Toft independently constructed $4$-critical graphs with minimum degree growing as $n^{1/3}$.
• Luo, Ma, and Yang obtained the upper bound $\delta(G)<0.328n$.
• Dirac constructed $6$-critical graphs with minimum degree greater than $n/2$; the analogous $5$-critical question remains open.

Recent claimed linear upper bound

GPT-5.5 Pro + harness was credited with the claimed inequality $8e(G)/n^2+\delta(G)/n\leq 3/2+o(1)$, implying $\delta(G)\leq(3/10+o(1))n$. This is a partial result, not a resolution, and remains unverified independently.

Current status (as of June 2026): The existence of $4$-critical graphs with minimum degree $\Omega(n)$ remains open; $n^{1/3}$ constructions and a claimed, unverified $0.3n$-type upper bound are known.