k-vertex-critical graphs in which every critical edge set is large: the last open case k=4 (Erdős #944)
Statement
A critical vertex, edge, or set of edges of a graph is one whose deletion lowers the chromatic number. Let $k\geq 4$ and $r\geq 1$. Must there exist a graph $G$ with chromatic number $k$ such that every vertex is critical, yet every critical set of edges has size $>r$? (For $r=1$ this asks for a graph in which deleting any vertex lowers the chromatic number but deleting any single edge does not.)
Acceptance. FULLY RESOLVES: settle the case $k=4$, the only case left open per the background: either prove that for every $r\geq 1$ there is a 4-vertex-critical graph whose every critical edge set has size $>r$ (an explicit construction family with proofs, or verified finite witnesses for each $r$ plus an argument covering all $r$), or prove that for some $r\geq 1$ no such graph exists. Machine-checkable proof preferred. ADVANCES: (a) a single explicit graph settling $k=4$, $r=1$ (the last open case of Dirac's conjecture): adjacency data plus a machine-checkable certificate — a proper 4-colouring, a proper 3-colouring of $G-v$ for every vertex $v$, and for every edge $e$ a verifiable UNSAT/DRAT certificate that $G-e$ is not 3-colourable; (b) a verified lower bound on the order of any such $k=4$, $r=1$ graph (exhaustive search below $N$ vertices with code and an exhaustiveness certificate); (c) for $k\geq 5$, improve either side of the Skottova–Steiner bounds on $f_k(n)$ stated in the background, with proof. Deliver the witness graph + verification code + certificates, or the proof file.
Background
Posed by Erdős [Er89e]; listed as open on erdosproblems.com/944 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'); it is Problem 91 in the UCSD Erdős graph-problems collection. A graph with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical. The case $r=1$ is Dirac's 1970 conjecture. Brown [Br92] proved the $r=1$ case for $k=5$; Lattanzio [La02] proved existence for all $k$ with $k-1$ not prime; independently Jensen [Je02] gave constructions for all $k\geq 5$. Martinsson and Steiner [MaSt25] proved the statement for every $r\geq 1$ when $k$ is sufficiently large in terms of $r$, and Skottova and Steiner [SkSt25] extended it to all $k\geq 5$ and $r\geq 1$. The single remaining case is $k=4$: even the existence of a 4-vertex-critical graph with no critical edge ($r=1$) is open. Erdős also posed a quantitative form: with $f_k(n)$ the largest $r$ such that some $k$-vertex-critical graph on $n$ vertices has no critical set of at most $r$ edges, does $f_k(n)\to\infty$? Skottova and Steiner proved this for $k\geq 5$, with $n^{1/3}\ll_k f_k(n)\ll_k n/(\log n)^C$ for an absolute constant $C>0$; for $k=4$ it is open whether $f_4(n)\geq 1$ ever holds. Related: Erdős #917 (erdosproblems.com/917) and #1032 (erdosproblems.com/1032). The attacker's tool: SAT-driven search for the $k=4$, $r=1$ witness — any candidate is finitely certifiable via a proper 4-colouring, proper 3-colourings of every vertex-deleted subgraph, and UNSAT certificates that no edge-deleted subgraph is 3-colourable.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #944 (T. F. Bloom) | website |
| REF-02 | Problem 91 in the Erdős graph problems collection (UCSD) | website |
| REF-03 | Formalised statement of Erdős #944 (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.