Erdős problem #944 — wave6r report
Date: 2026-07-27 (UTC)
Claim labels used throughout:
- (a) elementary-rigorous: proved in this report from definitions.
- (b) rigorous-modulo-named-theorem: depends on the explicitly cited result.
- (c) plausible/structural-unverified: an observation or literature-search
conclusion, not asserted as a theorem.
- (d) computational-only: established by the reproduced finite computation,
but not accompanied by a formal SAT proof certificate.
0. Mandatory live-page audit
I fetched the live page through the Bright Data browser path, not by datacentre
curl. The browser reached
erdosproblems.com/944 and its discussion
thread on 2026-07-27.
Live status:
- OPEN.
- 0 claimed proofs.
- “Currently working on this problem”: None.
- “Interested in collaborating”: None.
- The other displayed reaction/formalisation-worker markers are also None.
Thus the mandatory stop condition did not fire.
The page defines deletion-criticality by a strict decrease of chromatic number.
Here is its displayed question verbatim:
> 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\)?
In formulas, an edge set \(R\) is critical when
\(\chi(G-R)<\chi(G)\), and \(G\) is \(k\)-vertex-critical when
\(\chi(G)=k\) and \(\chi(G-v)=k-1\) for every vertex \(v\).
Results listed on the live page
- (b) Brown settled \(k=5,r=1\); Lattanzio settled the cases in which
\(k-1\) is not prime; Jensen settled every \(k\geq5,r=1\).
- (b) Martinsson and Steiner settled each fixed \(r\) for sufficiently
large \(k=k(r)\).
- (b) Skottova and Steiner settled every \(k\geq5,r\geq1\). Hence the
only open value of \(k\) is \(4\), already open for \(r=1\).
- (b) For the quantitative function on the page, Skottova and Steiner
prove \(f_k(n)\to\infty\) for \(k\geq5\), with
\[ n^{1/3}\ll_k f_k(n)\ll_k \frac{n}{(\log n)^C}, \]
where \(C>0\) is absolute.
- The page identifies this as Problem 91 in the older graph-problem
collection and links Problems 917 and 1032.
The two live comments
1. (d) A comment dated 2026-06-18 points to
arXiv:2606.18462. It reports an exact
census of 6-regular graphs through order 15, restrictions on nontrivial
6-edge-cuts, and the exclusion of bipartite cut shores. It explicitly says
that the 6-regular subproblem remains unresolved.
2. (c) A comment dated 2025-08-22 notes the \(k\)-dependence in the displayed
asymptotic bounds. The current LaTeX page already renders the bounds with
\(\ll_k\), and with an absolute logarithmic exponent.
Comments on the site are explicitly marked as unverified user content. The
first one was checked against the cited arXiv preprint before being used below.
1. Primary-source literature audit
The following sources were located and checked for the claims attributed to
them:
- Brown, A vertex critical graph without critical edges,
DOI 10.1016/0012-365X(92)90354-I:
its abstract gives a 5-vertex-critical example with no critical edge.
- Lattanzio, A note on a conjecture of Dirac,
DOI 10.1016/S0012-365X(02)00394-1:
its abstract states the \(k-1\) nonprime cases.
- Jensen, Dense critical and vertex-critical graphs,
the all-\(k\geq5\) consequence is also stated explicitly in the later primary
sources below.
- Jensen and Siggers, *On a question of Dirac on critical and vertex critical
graphs*, Math-Net full record and PDF:
it constructs arbitrarily large 4-vertex-critical graphs with
\(\Omega(n^2)\) noncritical edges and only \(O(n)\) critical edges.
- Martinsson and Steiner, Vertex-critical graphs far from edge-criticality,
arXiv:2310.12891, Theorem 1: every fixed
\(r\) works for all sufficiently large \(k\).
- Skottova and Steiner, Critical edge sets in vertex-critical graphs,
arXiv:2508.08703: all \(k\geq5\) and
\(r\geq1\), the quantitative bounds, and Proposition 5.1 below.
- Ferudun, *Exact 6-cut rigidity and small-order superconnectivity for the
6-regular case of Dirac's \(k=4\) problem*,
arXiv:2606.18462: the preprint and its
ancillary source archive exist and contain the claims summarized by the
newest live comment.
Targeted searches for the exact problem, the phrase “6-regular
4-vertex-critical”, and post-2025 work on Dirac's \(k=4\) case found no claimed
resolution later than arXiv:2606.18462. (c) This is a documented search
miss, not a proof that no other relevant manuscript exists.
Two current structural facts guide the computation:
- (b) Skottova--Steiner Proposition 5.1 gives
\(\lambda(G)\geq3r+3\), hence \(\delta(G)\geq3r+3\), for every
\((4,r)\)-graph. For \(r=1\), degree 6 is the sparsest possible case, and
their Problem 5.2 asks whether a 6-regular example exists.
- (d, prior computation) arXiv:2606.18462 reports that among all 6-regular
graphs of order at most 15 there is only one 4-vertex-critical graph, at
order 13, and it has 13 critical edges. Thus it reports no 6-regular target
through order 15. The computation below does not ingest that graph or those
census files.
2. New finite result
Computational theorem
(d) Let
\[ C(n;a,b,c)=\operatorname{Cay}\!\left( \mathbb Z_n,\{\pm a,\pm b,\pm c\}\right) \]be a simple 6-regular circulant. If \(7\leq n\leq80\) and
\(C(n;a,b,c)\) is 4-vertex-critical, then it has at least one full
distance-orbit of critical edges. Consequently:
1. no 6-regular circulant \((4,1)\)-graph has order at most 80; and
2. every 4-vertex-critical graph in this finite class has at least \(n\)
critical edges, hence at least one third of its \(3n\) edges are critical.
The edge bound is sharp within the computed class: \(C(13;1,2,5)\) has exactly
one critical distance-orbit, hence exactly 13 critical edges.
This extends the unrestricted order-15 census only inside the substantial but
special class of circulant graphs. It does not settle the 6-regular
subproblem, much less Problem #944.
3. Elementary reductions used by the checker
3.1 Complete parametrisation of the searched class
(a) An undirected circulant has a symmetric nonzero connection set
\(S=-S\subseteq\mathbb Z_n\). A non-self-inverse generator occurs with its
negative and contributes degree 2. When \(n\) is even, \(n/2\) is the unique
nonzero self-inverse element; including it would make \(|S|\) odd. Therefore
every degree-6 connection set consists of exactly three pairs
\[ S=\{\pm a,\pm b,\pm c\},\qquad 1\leq aconnected, so omitting triples with larger gcd loses no target.
Thus iterating these triples is a complete enumeration of the relevant
circulants, although different triples can still define isomorphic unlabeled
graphs. All counts below are deliberately counts of canonical distance
triples, not isomorphism classes; duplication cannot invalidate a zero count.
3.2 Vertex-transitivity reduction
(a) Translation acts transitively on \(C(n;a,b,c)\). Hence all
vertex-deleted subgraphs are isomorphic. Such a circulant is
4-vertex-critical exactly when:
- \(G\) is not 3-colourable; and
- \(G-0\) is 3-colourable.
Indeed the second condition gives \(\chi(G)\leq4\) by assigning a fourth colour
to 0, while the first gives equality; translation handles every deleted
vertex.
3.3 Exact singleton criterion for critical edges
(a) Let \(G\) be 4-vertex-critical and \(uv\in E(G)\). Then \(uv\) is
critical if and only if some proper 3-colouring of \(G-v\) makes \(u\) the
unique neighbour of \(v\) in its colour.
- If such a colouring exists, give \(v\) the colour of \(u\) after deleting
\(uv\); this 3-colours \(G-uv\).
- Conversely, in a 3-colouring of \(G-uv\), the endpoints must have equal
colours, since otherwise the colouring would also colour \(G\). No other
neighbour of \(v\) can have that colour, since its edge to \(v\) remains.
For a circulant, translations and reflection \(x\mapsto-x\) make the edges at
distance \(d\) one orbit. It is therefore enough to test
\((0,a),(0,b),(0,c)\). A positive singleton witness for one representative
certifies all \(n\) edges in that orbit as critical.
4. Exact census
The verifier considered 171,551 connected distance triples over
\(7\leq n\leq80\). Its exhaustive partition was:
| Classification of a distance triple | Count |
|---|---:|
| \(G\) is 3-colourable | 129,753 |
| \(G\) and \(G-0\) are both non-3-colourable | 35,992 |
| \(G\) is 4-vertex-critical | 5,806 |
| Total | 171,551 |
Across the 5,806 vertex-critical triples, the program found 6,448 critical
distance-orbit incidences and zero triples with no critical orbit.
Only the following orders have any 4-vertex-critical triples. Every omitted
order in \(7,\ldots,80\) has count zero.
| \(n\) | 4-VC triples | Critical-orbit incidences | Target triples |
|---:|---:|---:|---:|
| 13 | 6 | 6 | 0 |
| 16 | 4 | 4 | 0 |
| 19 | 27 | 27 | 0 |
| 22 | 15 | 15 | 0 |
| 25 | 60 | 60 | 0 |
| 28 | 30 | 30 | 0 |
| 31 | 120 | 135 | 0 |
| 34 | 64 | 64 | 0 |
| 37 | 216 | 234 | 0 |
| 40 | 68 | 72 | 0 |
| 43 | 294 | 315 | 0 |
| 46 | 154 | 154 | 0 |
| 49 | 357 | 399 | 0 |
| 52 | 168 | 168 | 0 |
| 55 | 260 | 260 | 0 |
| 58 | 280 | 294 | 0 |
| 61 | 600 | 690 | 0 |
| 64 | 224 | 224 | 0 |
| 67 | 660 | 693 | 0 |
| 70 | 180 | 180 | 0 |
| 73 | 936 | 1,224 | 0 |
| 76 | 342 | 342 | 0 |
| 79 | 741 | 858 | 0 |
| Total | 5,806 | 6,448 | 0 |
(d) In this finite range, 4-vertex-critical triples occur only for
\(n\equiv1\pmod3\). No uniform claim is made from that pattern.
5. Reproduction and independent checks
The standalone verifier is
Run:
python runs/erdos944_wave6r_verify.py --max-n 80
The completed run used Python 3.12.3, python-sat 1.9.dev7, and one Intel Xeon
Platinum 8259CL core. Wall time was 323.463 seconds. The script's SHA-256 was
c438701e0d956b1b4c2642e9a2567dc455b347e719c8644283122d7646d89898
Verification design:
1. The script constructs every graph and every CNF from the integers
\(n,a,b,c\); it reads no graph database or paper certificate.
2. It asserts \(3n\) distinct edges and degree exactly 6 for every generated
graph.
3. Colour variables \(x_{v,i}\) and guarded activity variables encode proper
3-colourings. Assumptions with all vertices active test \(G\); changing the
sign of the activity literal for 0 tests \(G-0\).
4. Every SAT model is decoded and checked edge-by-edge outside the SAT solver.
Singleton witnesses are additionally checked directly on \(N(0)\).
5. Every UNSAT decision, and every SAT/UNSAT critical-orbit decision, is run
through both CaDiCaL 1.5.3 and Glucose 4.2. They agreed on every call.
6. The three top-level classifications are asserted to partition the generated
triples. A fresh order-80 run then checks the four aggregate regression
values \(171551,5806,6448,0\).
The two solvers are independent algorithms, but no DRAT/LRAT traces were
retained. The result is therefore honestly labelled (d) computational-only,
not a machine-checked theorem.
As a low-order external sanity check, the six order-13 circulant
parametrisations each have exactly one critical orbit. This agrees with the
unrestricted order-13 result reported in arXiv:2606.18462, but that agreement
is not used in the census.
6. Exact remaining wall
There are three distinct gaps.
1. Uniform circulant gap. The finite computation would become a theorem
for all degree-6 circulants if one proved:
> If \(C(n;a,b,c)-0\) is 3-colourable but \(C(n;a,b,c)\) is not, then some
> 3-colouring of the deleted graph has a singleton colour on
> \(\{\pm a,\pm b,\pm c\}\).
By Section 3.3 this is exactly the missing lemma saying that a critical
distance-orbit must exist. The finite \(n\equiv1\pmod3\) pattern does not
supply the needed uniformity.
2. Noncirculant degree-6 gap. Even a proof of that lemma would not settle
Skottova--Steiner Problem 5.2. The known enumeration jumps from
1,470,293,675 connected 6-regular graphs at order 15 to
113,314,233,808 at order 16; see Meringer's
A blind order-16 extension at a realistic sustained
\(5\times10^4\)–\(2\times10^5\) generated-and-classified graphs/second would
cost roughly 160–630 core-hours, before independent certification. I did
not run it.
3. Full problem gap. A \((4,1)\)-graph need only have minimum degree 6; it
need not be regular or vertex-transitive. Moreover Problem #944 asks every
\(r\), while even \(k=4,r=1\) is open. The present computation neither
constructs a target nor rules out those broader graph classes.
The concrete progress is therefore a checked obstruction in a natural
symmetry class, together with an exact singleton lemma identifying what a
uniform circulant argument must prove.
PARTIAL: Exhaustively cross-checked all 171,551 connected 6-regular circulant parameter triples through order 80; every one of the 5,806 four-vertex-critical cases has a critical edge orbit, so no circulant target occurs in this range.