Erdős problem 917 — live audit, exact small cases, and a two-obstruction reduction

Date: 2026-07-27 UTC

Claim labels used throughout:

• (a) elementary-rigorous: proved here from definitions.
• (b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the named published theorem.
• (c) plausible/structural-unverified: a search result, heuristic, or non-exhaustive observation, not a theorem.
• (d) computational-only: an exhaustive computation or machine-checked finite assertion, with its dependency stated.

No claim below is intended to close the asymptotic problem.

0. Mandatory live-page check

(d, live observation) I accessed erdosproblems.com/917 and its LaTeX view on 2026-07-27 through the Bright Data browser path. The live page says OPEN, 0 comments, 0 claimed proofs, Interested in collaborating: None, and Currently working on this problem: None. It also has None for likes, “looks difficult,” “looks tractable,” “results could be formalisable,” and “working on formalising”; the formalised-statement field is No. Thus none of the mandatory stop conditions applies.

Here is the problem statement verbatim from the live LaTeX view (only line wrapping has been added):

> Let $k\geq 4$ and $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has chromatic number $k$ and is critical (i.e. deleting any edge reduces the chromatic number).

>

> Is it true that

> \[ > f_k(n) \gg_k n^2? > \]

> Is it true that

> \[ > f_6(n)\sim n^2/4? > \]

> More generally, is it true that, for $k\geq 6$,

> \[ > f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2? > \]

(d, live-page transcription) The listed known results are:

1. Dirac [Di52] gives

\[ f_6(4n+2)\geq 4n^2+8n+3 \]

by joining two copies of \(C_{2n+1}\).

2. Erdős [Er69b] generalises this for \(3\mid k\), on infinitely many orders \(n=mk/3\) with \(m\) odd:

\[ f_k(n)\geq \frac12\left(1-\frac1{k/3}\right)n^2+n. \]

3. Toft [To70] proved \(f_k(n)\gg_k n^2\) for every \(k\geq4\). Thus the first displayed question has already been answered affirmatively.

4. The page attributes constructions to Stiebitz [St87] which disprove the displayed general asymptotic for \(k\not\equiv0\pmod3\). The live source literally prints the three corrections as \(0,1/7,\) and @@S31@@.

5. Stiebitz's listed upper bound is

\[ f_k(n)<\operatorname{ex}(n;K_{k-1}) \sim \frac12\left(1-\frac1{k-2}\right)n^2. \]

6. Luo–Ma–Yang [LMY23] improve it to

\[ f_k(n)\leq \frac12\left(1-\frac1{k-2} -\frac1{36(k-1)^2}+o(1)\right)n^2. \]

The page also points to problems 944 and 1032.

Consequently the live \(k=6\) question remains the clean unresolved part relevant here.

1. Literature audit

(b, primary source checked) Cong Luo, Jie Ma, and Tianchi Yang, On the maximum number of edges in \(k\)-critical graphs, arXiv:2301.01656, Combinatorics, Probability and Computing 32 (2023), 900–911, DOI 10.1017/S0963548323000238, exists and was inspected in full. Its abstract says the maximum-edge problem is widely open for every fixed \(k\geq4\). Its Theorem 1.1 is the upper bound quoted on the live page. Its introduction also explicitly says that it is not known whether

exists for any \(k\geq4\). In particular, that paper does not settle the \(k=6\) limit.

(b, primary source checked) Wesley Pegden, Critical graphs without triangles: an optimum density construction, arXiv:1101.4417, proves density \(1/4-o(1)\) for the restricted class of triangle-free \(k\)-critical graphs when \(k\geq6\). This supplies a strong restricted lower construction, not an unrestricted upper bound, so it does not settle problem 917.

(b, publication metadata and primary article checked) Dirac's paper exists as G. A. Dirac, A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs, J. London Math. Soc. 27 (1952), 85–92, DOI 10.1112/jlms/s1-27.1.85. The Dirac construction is stated both on the live page and in the inspected Luo–Ma–Yang paper.

(b, bibliographic existence checked; full original text not located) Toft's 1970 paper exists as B. Toft, On the maximal number of edges of critical \(k\)-chromatic graphs, Studia Sci. Math. Hungar. 5 (1970), 461–470. I did not locate an accessible scan of the original article. Luo–Ma–Yang cite it as reference [12] and attribute the explicit general lower constructions to Toft. This differs from the current web page's attribution of those constructions to Stiebitz [St87]. I record the discrepancy rather than silently choosing one attribution; it does not affect the \(k=6\) arguments below.

(b/d, independent small-graph source checked) A. G. Luiz and R. B. Richter, Remarks on a conjecture of Barát and Tóth, Electronic J. Combin. 21(1) (2014), P1.57, reports Royle's small-critical-graph lists, including 231 non-universal 6-critical graphs on 11 vertices. The current ANU edge-critical graph catalogue gives 393 total edge-6-critical graphs on 11 vertices and links both the graph6 files and Olivier Lalonde's generator source. The difference is consistent with the 2014 paper listing the no-universal cores in that particular count. This catalogue is an external computational source, not a proof substituted for the fresh census below.

(c, honest search miss) Exact-title, exact-formula, forward-citation, arXiv, publisher, and web searches through 2026-07-27 found no later primary paper improving the unrestricted \(k=6\) asymptotic beyond Luo–Ma–Yang or claiming a solution. This is a search report, not a proof of absence. The live page's current OPEN/zero-claims status is the authoritative status check for this run.

2. Removing the isolated-vertex ambiguity

The page's literal edge-only definition allows isolated vertices.

Lemma 2.1 (a). If \(G\) is edge-critical with \(\chi(G)=k\), then all its edges lie in one connected component. Every vertex in that component has degree at least \(k-1\), and deleting any one of its vertices reduces the chromatic number. Thus, after deleting the isolates, one obtains a standard \(k\)-critical graph (every proper subgraph is \((k-1)\)-colourable). Conversely, adding any number of isolates to a standard \(k\)-critical graph preserves the page's edge-critical property.

Proof. A component of chromatic number \(k\) survives deletion of any edge in another nontrivial component, so no second nontrivial component is possible. Let \(v\) be non-isolated and choose an incident edge \(e\). Since \(G-e\) is \((k-1)\)-colourable and \(G-v\subseteq G-e\), \(G-v\) is \((k-1)\)-colourable. If \(d(v)\leq k-2\), one of the \(k-1\) colours is absent from \(N(v)\), so this colouring extends to \(G\), a contradiction. Hence \(d(v)\geq k-1\). Edge and vertex deletion now cover every proper subgraph. The converse is immediate. \(\square\)

Therefore, if \(c_k(r)\) is the maximum edge count of a non-isolated standard \(k\)-critical core of order exactly \(r\), with \(c_k(r)=-\infty\) when none exists, the page's literal function is

This is why the exhaustive search only needs connected graphs of minimum degree at least five for \(k=6\).

3. Fresh exact census for \(f_6(n)\), \(6\leq n\leq11\)

Method and completeness

(d) The standalone checker is erdos917_wave6q_verify.py. It does the following for every core order \(r\leq11\):

1. Calls Debian nauty-geng 2.8.8 with -c -d5, one edge count at a time in descending order. Thus nauty produces one representative of every isomorphism class satisfying the necessary connectedness and minimum-degree conditions.

2. Parses graph6 in code written in the checker.

3. Uses an exact DSATUR backtracker written in the checker to reject 5-colourable graphs and to verify that every edge deletion is 5-colourable.

4. Uses only necessary filters (minimum degree, absence of a proper \(K_6\), and vertex-deletion colourability) before the definitive edge tests. A filter can only reject a graph that Lemma 2.1 already rules out.

5. Stops at the first edge count containing a critical graph. All higher edge counts have then been exhausted. Equation (2.1) allows the search at a new order to stop at the best smaller-order value.

(d, independent algorithmic audit) A second fixed-order colouring backtracker, which does not share DSATUR's dynamic ordering or census filters, rechecks every reported extremal witness. The two colouring algorithms are also compared on every labelled graph on four vertices for \(k=1,2,3,4\). Positive controls \(K_6\), \(C_5\vee C_5\), and \(C_5\vee C_7\), and a negative \(K_7\) control, are built independently.

(d, third audit) A separate PySAT/Minisat22 encoding confirmed that the 11-vertex witness is not 5-colourable, is 6-colourable, and becomes 5-colourable after each of its 39 individual edge deletions.

The final fresh run took 81.74 seconds, used 16,268 KB maximum resident memory, and exited 0. At order 11 it exhausted 1,336,207 non-isomorphic candidates with 39 or more edges. The complete output is reproducible with:

python runs/erdos917_wave6q_verify.py

Exact computational result

(d, exhaustive modulo nauty's isomorph-free generation) The literal-page values are:

| \(n\) | \(f_6(n)\) | maximizing core order | graph6 witness | upper-interval classes checked at new order |

|---:|---:|---:|:---|---:|

| 6 | 15 | 6 | E~~w | direct \(K_6\) control |

| 7 | 15 | 6 plus one isolate | E~~w | 4 |

| 8 | 23 | 8 | GUZ~~{ | 24 |

| 9 | 27 | 9 | HEnbv~~ | 567 |

| 10 | 35 | 10 | IUZ~vz}}o | 3,530 |

| 11 | 39 | 11 | JCxu}z}nvz? | 1,336,207 |

At each attained core maximum the checker found exactly one isomorphism class. This is a finite computational statement, not an asymptotic theorem.

An explicit description of the 11-vertex extremizer is useful. On vertices \(0,\ldots,10\), take \(K_{11}\) and delete exactly

(d) The checker recomputes \(55-16=39\) edges, degree sequence

non-5-colourability, a 5-colouring after every one of the 39 edge deletions, and connectedness of its complement. The last property means this 11-vertex extremizer is join-indecomposable.

(d, external cross-check) Independently downloading the current ANU catalogue files gives total 6-critical-core counts \(1,0,1,2,22,393\) at orders \(6,\ldots,11\); maximizing those files gives exactly the same five core witnesses and edge counts. The 11-vertex file had SHA-256

at access time. The same external catalogue gives the unique order-12 maximum \(47\), namely \(C_5\vee C_7\), among 17,036 listed cores. I do not promote the order-12 value to the fresh-census table because I checked that catalogue but did not independently regenerate its completeness with the raw Python/geng route.

4. A clean reduction of the \(k=6\) asymptotic

For disjoint graphs \(A,B\), write \(A\vee B\) for their complete join.

Lemma 4.1 (a).

For non-isolated standard critical graphs, \(A\vee B\) is critical if and only if both factors are critical.

The chromatic formula follows because colours cannot be shared across the join. For an internal deleted edge, use a reduced colouring of that factor and an ordinary colouring of the other. For a deleted cross-edge \(uv\), colour \(A-u\) and \(B-v\) with disjoint palettes of \(a-1\) and \(b-1\) colours and give \(u,v\) one shared fresh colour; this uses \(a+b-1\) colours. Conversely, if a factor had a proper subgraph of the same chromatic number, joining it to the other factor would give a proper subgraph of the join with unchanged chromatic number. A graph has disconnected complement exactly when it is a nontrivial complete join.

Lemma 4.2 (a). Under the page's literal convention,

for every \(n\), not merely on Dirac's equal-cycle subsequence.

Indeed, for even \(n\), join odd cycles of balanced lengths \(a+b=n\). This has \(ab+a+b\) edges: \(n^2/4+n\) when \(n\equiv2\pmod4\), and \(n^2/4+n-1\) when \(n\equiv0\pmod4\). For odd \(n\), use the even construction on \(n-1\) vertices and add an isolate. Thus the \(k=6\) question is entirely an upper-bound question under the live statement.

Define \(I_6(n)\) to be the maximum number of edges in a page-admissible graph on \(n\) vertices whose non-isolated 6-critical core has connected complement (equivalently, is join-indecomposable).

Reduction theorem 4.3 (b, using Luo–Ma–Yang only for \(k=4\)). The live conjecture

is equivalent to the conjunction of the following two upper bounds:

Necessity (a). Clearly \(I_6(n)\leq f_6(n)\). To transfer (4.1) to \(f_5\), take a core attaining \(f_5(n)\), join it with \(K_1\), and add enough isolates to reach \(n+1\) vertices. The result is page-admissible and 6-critical on its non-isolated core, so

Equation (4.1) implies (L5).

Sufficiency (a/b). Let \(H\) be the non-isolated core of any page-admissible 6-critical graph.

• If \(\overline H\) is connected, apply (I6).
• If \(\overline H\) is disconnected, group its join factors as \(H=A\vee B\) with

\[ (\chi(A),\chi(B))\in\{(1,5),(2,4),(3,3)\}. \]

Standard 1-, 2-, and 3-critical graphs are respectively \(K_1,K_2,\) and odd cycles. Hence the three cases give

\[ e(H)\leq \begin{cases} f_5(r-1)+(r-1),&\chi(A)=1,\\ f_4(r-2)+2r-3,&\chi(A)=2,\\ r^2/4+r,&\chi(A)=3, \end{cases} \]

where \(r=|H|\).

The first line is at most \((1/4+o(1))r^2\) by (L5). In the second line, the live Luo–Ma–Yang bound at \(k=4\) has coefficient

and the \(2r-3\) term is lower order. The third line is immediate. Isolates and replacing \(r\) by \(n\) cannot increase the leading coefficient. Combining this upper bound with Lemma 4.2 proves (4.1). \(\square\)

This reduction is exact at the level of leading coefficients: no other join-decomposable obstruction exists.

5. The precise wall

(b) The two genuinely missing uniform lemmas are now explicit:

1. (L5): improve the best cited general 5-critical upper coefficient from

\[ \frac12\left(1-\frac13-\frac1{36\cdot16}\right) =\frac{383}{1152}\approx0.332465 \]

to \(1/4+o(1)\).

2. (I6): prove the \(1/4+o(1)\) upper bound for complement-connected 6-critical cores. The cited general \(k=6\) coefficient is

\[ \frac12\left(1-\frac14-\frac1{36\cdot25}\right) =\frac{337}{900}\approx0.374444, \]

which is far from \(1/4\).

(d) The arithmetic fractions and their gaps above are recomputed with exact Fraction arithmetic in the standalone checker. The 11-vertex extremizer has connected complement, so (I6) is not a vacuous class. Conversely, a finite census through any fixed order supplies no uniform control as \(n\to\infty\); it cannot close either missing lemma.

(d, computation cost) The raw order-12 route would have to inspect roughly 29 million connected minimum-degree-five isomorphism classes at 48 or more edges. Extrapolating from the audited Python throughput gives about 25–35 CPU minutes (roughly \(0.4\)–\(0.6\) core-hours) on this VM, beyond the stipulated few-minute run budget, so I did not run it. Lalonde's specialised critical-graph generator and its public order-12 catalogue are much more efficient, but importing that catalogue is not an independent regeneration of completeness.

(c) I found no credible finite-pattern extrapolation that attacks (L5) or (I6). The standard join construction explains the \(1/4\) lower coefficient but gives no upper control on join-indecomposable cores; Luo–Ma–Yang's local matching structure is not presently strong enough to bridge the displayed coefficient gaps. Any claimed solution still needs one uniform argument covering both named obstructions.

PARTIAL: Exhaustively verified \(f_6(6),\ldots,f_6(11)=15,15,23,27,35,39\), exhibited the unique 11-vertex 39-edge core, and reduced \(f_6(n)\sim n^2/4\) exactly to the two missing upper bounds (L5) and (I6); neither uniform bound is proved.