Erdős problem #1032: live check, exact small cases, and a finite-seed construction

Access/search date: 2026-07-27 UTC.

Result in one paragraph

The problem is still open; nothing below proves or disproves linear minimum degree. The verified progress is:

1. a computationally exact small-order table for the literal page parameter through \(n=14\):

\[ (g(4),\ldots,g(14))=(3,0,3,3,3,3,3,3,4,4,4); \]

2. explicit graph6 certificates for all minimum-degree-\(4\) extremizers at orders \(12,13,14\);

3. an elementary Hajós-join reduction which upgrades Simonovits's even-order theorem to minimum degree \(\Omega(n^{1/3})\) at every sufficiently large order;

4. a second use of that reduction which turns the three consecutive finite seed orders into an explicit edge-\(4\)-critical graph of minimum degree at least \(4\) for every \(n\ge 56\);

5. an exact diagnosis of the remaining asymptotic wall: the known lower bound is \(\Omega(n^{1/3})\), while the May 2026 comment-linked upper bound is only \((3/10+o(1))n\). A negative solution needs the missing uniform statement \(g(n)=o(n)\); a positive solution needs a construction retaining a positive minimum-degree density.

This report uses the requested labels:

• [A] elementary-rigorous;
• [B] rigorous modulo the explicitly named theorem/artifact;
• [C] plausible or structural but unverified;
• [D] computational-only.

0. Mandatory live-page gate

I fetched the live problem page, its LaTeX view, and its discussion thread through a Bright Data cloud browser, not datacenter curl.

The live status was OPEN. It displayed:

• 0 claimed proofs for this problem;
• Interested in collaborating None;
• Currently working on this problem None;
• page last edited 23 January 2026.

Thus the stop/collision rule did not fire.

Verbatim live statement

> 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\).

>

> Is there, for arbitrarily large \(n\), a \(4\)-chromatic critical graph on \(n\) vertices with minimum degree \(\gg n\)?

Verbatim live remarks/known results

> In \([Er93]\) Erdős said he asked this 'more than 20 years ago'.

>

> Dirac gave an example of a \(6\)-chromatic critical graph with minimum degree \(>n/2\). This problem is also open for \(5\)-chromatic critical graphs.

>

> Simonovits \([Si72]\) and Toft \([To72]\) independently constructed \(4\)-chromatic critical graphs with minimum degree \(\gg n^{1/3}\). Toft conjectured that a \(4\)-chromatic critical graph on \(n\) vertices has at least \((\frac{5}{3}+o(1))n\) vertices, and has examples to show this would be the best possible.

>

> See also [917] and [944].

The word “vertices” in the second occurrence is what the live LaTeX page actually says. The last displayed discussion reply says, verbatim, “Sorry, my fault, should say edges in the second.”

Everything displayed in the discussion

The rendered thread contained the following items:

• Lech Mazur, 07:06 on 07 May 2026: “GPT-5.5 Pro + harness proposes a note giving an apparently new partial bound: a \(3/10\) minimum-degree bound for 4-critical graphs.” It links a note and Lean artifact and states

\[ \frac{8e(G)}{n^2}+\frac{\delta(G)}n\le\frac32+o(1), \qquad \delta(G)\le\left(\frac3{10}+o(1)\right)n. \]

• Nat Sothanaphan, 14:00 on 07 May 2026: “Congrats. Standard check found no issues.” The reply says this improves the Luo--Ma--Yang consequence \(\delta(G)<0.328n\).
• An Unknown post at 19:53 on 13 Sep 2025 is displayed as [Post deleted].
• Thomas Bloom, 19:54 on 13 Sep 2025: “Sorry, my fault, should say edges in the second.”

No displayed item claims to settle the problem. [A: faithful live-page transcription; not a mathematical correctness endorsement of comments.]

1. Literal convention and a useful elementary reduction

Let \(G\) satisfy the page definition. Isolated vertices are not explicitly forbidden. This matters at \(n=5\).

Lemma 1 (one critical core plus isolates)

Every page-critical \(G\) consists of one connected, non-isolated edge-\(4\)-critical component \(C\), together with zero or more isolated vertices. [A]

Proof. Some component \(C\) has chromatic number \(4\). If an edge lay outside \(C\), deleting that edge would leave \(C\) and hence leave chromatic number \(4\), contrary to criticality. Thus every other component is an isolate. There cannot be a second \(4\)-chromatic component for the same reason. Every edge of \(C\) is critical, and \(C\) is connected by definition of component. \(\square\)

Lemma 2 (edge-critical equals proper-subgraph-critical on the core)

If \(C\) has no isolates and satisfies the page's edge-deletion definition, then every proper subgraph of \(C\) is \(3\)-colourable. [A]

Proof. A proper subgraph which omits an edge is contained in \(C-e\) for some omitted edge \(e\). If it instead omits a vertex \(v\), choose an edge \(e\) incident with \(v\); the subgraph is again contained in \(C-e\). Every \(C-e\) is \(3\)-colourable. The reverse implication is immediate. \(\square\)

Consequently the proper-subgraph convention in modern papers and the page convention agree for the non-isolated cores enumerated below. [A]

Lemma 3 (the core has minimum degree at least \(3\))

Every non-isolated \(4\)-critical core has \(\delta(C)\ge3\). [A]

Proof. By Lemma 2, \(C-v\) is \(3\)-colourable. If \(d(v)\le2\), one of the three colours is absent from \(N(v)\), so the colouring extends to \(v\), contradicting \(\chi(C)=4\). \(\square\)

Define

If a core exists at exact order \(n\), padding a smaller core with isolates cannot improve \(g(n)\). At \(n=5\), there is no five-vertex core, but \(K_4\) plus one isolate is literally page-critical and has minimum degree \(0\). Thus \(g(5)=0\), rather than “undefined.” [A, with the nonexistence of a five-vertex core also independently checked in the census.]

2. Primary-source literature check

Original problem and classical lower bound

Erdős's paper “Problems and Results on Chromatic Numbers in Finite and Infinite Graphs”, pp. 201--213 in the 1985 Wiley proceedings, explicitly asks whether there is a \(4\)-chromatic critical \(G(n)\) in which every vertex has degree \(>cn\), then states that Simonovits and Toft independently obtained degree \(>cn^{1/3}\). This is a primary source and directly matches the live problem. [B, primary-source transcription.]

The live citation [Er93] exists as Paul Erdős, “Some of my favorite solved and unsolved problems in graph theory,” Quaestiones Mathematicae 16 (1993), 333--350, DOI 10.1080/16073606.1993.9631741. [B, bibliographic verification.]

I downloaded the primary scan of Simonovits, “On colour-critical graphs”, Studia Sci. Math. Hungar. 7 (1972), 67--81. Its definition is exactly edge-critical. Theorem 5 states, for every sufficiently large even \(n\), the existence of a \(4\)-critical \(W^n\) with

The proof's clean infinite subfamily takes a parameter \(v\), has

and therefore also \(\delta(W^n)\ge v\). The checker independently verifies the arithmetic \(6(v^3+v^2+2v)\le(6v)^3\). [B for Simonovits Theorems 5--6; A for the arithmetic.]

The Toft paper exists as B. Toft, “Two theorems on critical 4-chromatic graphs,” Studia Sci. Math. Hungar. 7 (1972), 83--89; it is also reference [4] in Simonovits's primary scan. I did not locate a trustworthy full-text scan in this search, so I do not attribute any finer theorem to it beyond the live page's claim and this verified bibliography. [B for existence; honest literature miss for finer content.]

Modern upper bounds

Cong Luo, Jie Ma, and Tianchi Yang, “On the maximum number of edges in \(k\)-critical graphs”, arXiv:2301.01656, published in Combinatorics, Probability and Computing 32 (2023), 900--911, DOI 10.1017/S0963548323000238, proves in Theorem 1.2

for sufficiently large \(n\), where \(f_4(n)\) is the maximum edge count of an \(n\)-vertex proper-subgraph-\(4\)-critical graph. Since \(2e(G)\ge n\delta(G)\), this gives

The paper also describes the dense Toft graph: two odd-cycle parts, two independent parts, a complete bipartite graph between the independent parts, and two perfect matchings. The odd-cycle vertices have degree exactly \(3\), so quadratic edge density by itself does not address minimum degree. [B for Theorem 1.2 and the construction; A for the arithmetic and degree calculation.]

The May 2026 discussion links a proof note and Lean repository at inspected commit

95011676d9788fe0f994a1231457e44a16216c98. The repository states the finite epsilon form of

and a proper-critical wrapper. Combining it with \(e(G)\ge n\delta(G)/2\) gives

hence \(\delta(G)\le(3/10+o(1))n\). I inspected the statements and proof note but did not rerun the large pinned Lean build; therefore I use this only as [B, modulo the named checked artifact], exactly as a partial result rather than a resolution.

Targeted searches for the exact problem phrase, the \(0.328\) bound, the \(3/10\) formula, and later \(4\)-critical minimum-degree work found the sources above but no primary paper claiming an affirmative construction, an \(o(n)\) upper bound, or a solution. This is an honest search result, not proof that no such paper exists. [C as a literature-completeness claim.]

3. Exact small-order computation

Data source and what “exact” means here

Brendan McKay's Combinatorial Data graph page says that its edge-critical files are all simple graphs with no isolates satisfying the same edge-critical definition, generated by Olivier Lalonde. It lists the complete \(k=4\) catalogues through order \(14\) and links the gencrit source. The source was inspected and rebuilt at commit

6bf7a836ec832b08c5053273b80b2ef240bd56ec.

The following table is [D]. “Exact” means exhaustive modulo correctness/completeness of nauty and gencrit, not a hand proof of the absence of another graph.

| \(n\) | non-isolated critical cores | core minimum-degree distribution | literal \(g(n)\) |

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

| 4 | 1 | \(1\) with \(\delta=3\) | 3 |

| 5 | 0 | empty | 0 |

| 6 | 1 | \(1\) with \(\delta=3\) | 3 |

| 7 | 2 | \(2\) with \(\delta=3\) | 3 |

| 8 | 5 | \(5\) with \(\delta=3\) | 3 |

| 9 | 21 | \(21\) with \(\delta=3\) | 3 |

| 10 | 150 | \(150\) with \(\delta=3\) | 3 |

| 11 | 1,221 | \(1{,}221\) with \(\delta=3\) | 3 |

| 12 | 14,581 | \(14{,}580\) with \(\delta=3\); \(1\) with \(\delta=4\) | 4 |

| 13 | 207,969 | \(207{,}968\) with \(\delta=3\); \(1\) with \(\delta=4\) | 4 |

| 14 | 3,567,180 | \(3{,}567{,}178\) with \(\delta=3\); \(2\) with \(\delta=4\) | 4 |

The first core with no degree-\(3\) vertex occurs at order \(12\). The order-\(13\) degree-\(4\) core is triangle-free; the order-\(12\) one is not. [D]

Explicit extremizers

These are standard graph6 strings. The verifier implements graph6 decoding itself and checks every edge deletion.

| \(n\) | graph6 | \(e\) | degree sequence | triangles |

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

| 12 | <code>K?&#96;FAommCiM_</code> | 24 | \(4^{12}\) | 4 |

| 13 | <code>L?&#96;DE&#96;gl@YJODg</code> | 26 | \(4^{13}\) | 0 |

| 14 | <code>M?AEB?wL?UrGtGZ_?</code> | 29 | \(4^{12},5^2\) | 3 |

| 14 | <code>M?ABAaQHW{TGu?Z??</code> | 28 | \(4^{14}\) | 0 |

Because backticks occur inside two graph6 strings, their unambiguous Python byte literals are:

b"K?`FAommCiM_"
b"L?`DE`gl@YJODg"
b"M?AEB?wL?UrGtGZ_?"
b"M?ABAaQHW{TGu?Z??"

For a package-independent explicit representation, the order-\(12\) seed has vertices \(0,\ldots,11\) and edges

04 06 09 0-10
15 16 17 1-11
26 28 29 2-11
37 39 3-10 3-11
47 48 49
58 5-10 5-11
68
7-10

Here, for example, 0-10 means \(\{0,10\}\), while 04 means \(\{0,4\}\). The standalone checker is the authoritative parser/certificate. [D]

Independent checks actually run

The verifier does not use NetworkX or a SAT package. It contains:

• its own graph6 decoder/encoder;
• an exact DSATUR \(k\)-colouring backtracker;
• a second fixed-order colouring backtracker;
• direct validation of returned \(3\)-colourings;
• the literal predicate “not \(3\)-colourable, and every \(G-e\) is \(3\)-colourable”;
• a fast packed-bit degree scanner.

Three runs were made.

1. Full default:

python3 -u runs/erdos1032_wave6t_reverify.py

This took 62.52 wall seconds / 49.62 CPU seconds. It:

• generated and filtered every nonisomorphic connected graph of minimum degree at least \(3\) through \(n=9\);
• saw respectively \(1,3,19,150,2589,84242\) candidates at orders \(4,\ldots,9\);
• obtained exactly \(1,0,1,2,5,21\) critical cores and exact graph6-set equality with the independent catalogue;
• audited every catalogue graph through \(n=12\);
• scanned all 207,969 and 3,567,180 records at orders \(13,14\);
• audited every degree extremizer through \(14\) with both colouring implementations.

2. Pinned source regeneration:

python3 -u runs/erdos1032_wave6t_reverify.py \
  --full-audit-max 11 --build-gencrit

This downloaded checksum-pinned nauty 2.9.3 and gencrit.c, built them, regenerated every core through order \(11\), and got exact set equality. The order-\(11\) regenerated sorted stream had SHA-256

2db3652276b6b37a150455c605a0d3e7d2afafc04ef5e9f0aee5c70dd57d2374

3. Recursive-construction audit:

python3 -u runs/erdos1032_wave6t_reverify.py \
  --catalog-max 12 --full-audit-max 4 --direct-max 4 \
  --hajos-demo-order 56

It built the \(n=56\) graph below from five order-\(12\) seeds and checked from scratch:

n=56, e=116, delta=4, exact edge-critical audit PASS

The standalone code is erdos1032_wave6t_reverify.py. [D]

Computational limitations

For \(n\le9\), the independent path enumerates all necessary nauty candidates and applies the Python predicate. Through \(n=11\), the independently rebuilt gencrit output equals the hosted catalogue exactly. At \(n=12\), every hosted record was property-audited, but catalogue completeness rests on the generator. At \(n=13,14\), every record was degree-scanned and every extremizer was double-audited; membership of every non-extremal record was not rechecked because it is irrelevant to the displayed maximum, but completeness still rests on the catalogue. [D]

The code therefore does not turn the table into a human theorem independent of nauty/gencrit. It also cannot turn finitely many values into an asymptotic answer.

4. Two Hajós-join consequences

This is weaker than Simonovits's \(\Omega(n^{1/3})\) theorem, but it is a clean consequence of the newly extracted consecutive seeds and is completely explicit.

Hajós-join lemma

Let \(G_1,G_2\) be edge-\(4\)-critical graphs, and choose edges \(x_1y_1\in E(G_1)\), \(x_2y_2\in E(G_2)\). Delete those edges, identify \(x_1,x_2\) to one vertex \(x\), and add \(y_1y_2\). Call the result \(H\).

Then \(H\) is edge-\(4\)-critical, has

and

[A]

Proof. In every \(3\)-colouring of \(G_i-x_iy_i\), the two endpoints \(x_i,y_i\) have the same colour; otherwise restoring the edge would \(3\)-colour \(G_i\). If \(H\) had a \(3\)-colouring, then \(x,y_1,y_2\) would all have the same colour, contradicting the new edge \(y_1y_2\).

It remains to colour every edge deletion from \(H\).

• If the deleted edge is the new \(y_1y_2\), combine \(3\)-colourings of \(G_1-x_1y_1\) and \(G_2-x_2y_2\), permuting colours so the two copies of \(x\) agree.
• If the deleted edge \(f\) came from \(G_1\), colour \(G_1-f\). The retained edge \(x_1y_1\) forces \(x_1,y_1\) to have different colours. Combine this with a \(3\)-colouring of \(G_2-x_2y_2\), in which \(x_2,y_2\) have the same colour, aligning \(x_1,x_2\). The new edge \(y_1y_2\) is then proper.
• The \(G_2\) case is symmetric.

Thus \(H-f\) is \(3\)-colourable for every edge \(f\), while \(H\) is not. Such a colouring of any \(H-f\) also shows \(\chi(H)\le4\) by assigning one endpoint of \(f\) a fresh fourth colour. Hence \(\chi(H)=4\) and \(H\) is edge-critical.

Every vertex other than the identified \(x\) keeps its degree: each \(y_i\) loses \(x_i\) and gains the other \(y\), and all other vertices are untouched. The identified vertex has degree

This proves the degree bound. \(\square\)

Uniform-order corollary of Simonovits

Simonovits's Theorem 5 gives, for every sufficiently large even \(m\), an edge-\(4\)-critical graph \(W^m\) with

For a sufficiently large odd \(n\), choose even \(m_1,m_2\) such that

Both can be made larger than the threshold in Simonovits's theorem, and

Apply the Hajós join to \(W^{m_1}\) and \(W^{m_2}\). Its order is \(n\). Once \(m_1,m_2\) are large enough that both input minimum degrees are at least \(2\), the degree formula gives

Together with the even-order theorem, this proves \(g(n)=\Omega(n^{1/3})\) for every sufficiently large integer \(n\), with one absolute constant. The use of Simonovits's theorem is [B]; the parity split and Hajós deduction are [A]. This strengthens the order-uniformity of the cited lower bound, not its exponent.

Closed form from the finite seeds

For \(n\ge56\), write

Set

Since \(q\ge5\) and \(b+c=\lceil r/2\rceil\le5\), one has \(a\ge0\), and

Take \(a\) copies of the order-\(12\) seed, \(b\) copies of the order-\(13\) seed, and \(c\) copies of either order-\(14\) seed, then repeatedly apply the Hajós join. Each join subtracts one from the sum of the orders, so the final order is

The Hajós lemma preserves minimum degree at least \(4\). Therefore:

> For every integer \(n\ge56\), there is an explicit edge-\(4\)-critical \(n\)-vertex graph with minimum degree at least \(4\).

The uniform join argument and semigroup arithmetic are [A]; existence/criticality of the three finite seeds is [D], so the displayed family as a whole is [D+A], not a purely handwritten theorem. The \(n=56\) instance was directly checked. This construction does not improve the classical \(\Omega(n^{1/3})\) asymptotic lower bound.

5. Why the standard machinery still stalls

The exact remaining alternatives can be stated sharply.

What an affirmative solution needs

It needs one constant \(c>0\) and infinitely many (or arbitrarily large) edge-\(4\)-critical graphs \(G\) satisfying

Neither quadratic edge count nor Hajós closure supplies this. The dense Toft construction has degree-\(3\) odd-cycle vertices. A Hajós join preserves the smaller input minimum degree while orders add, so iterating fixed seeds gives only bounded minimum degree. [A]

What a negative solution needs

It needs the uniform statement

Equivalently, it needs \(g(n)=o(n)\). The current \(3/10+o(1)\) upper bound is a constant-density ceiling and still permits every positive \(c<3/10\). [A for the implication, modulo the current bound as B.]

Thus the exact missing lemma is not another fixed constant improvement such as \(0.29n\). It is a mechanism forcing the coefficient to tend to zero, or a construction showing that it does not.

Why extending the census is not the missing step

The core counts grow

at orders \(12,13,14\). Extrapolating only the last observed output-count ratios suggests roughly \(6\times10^7\) to \(8\times10^7\) order-\(15\) records, about \(1.1\)--\(1.5\) GB uncompressed graph6 data. A measured order-\(12\) gencrit pilot produced 6,301 records in 196 CPU seconds before being stopped; crude output-rate extrapolation puts an order-\(15\) run around \(600\) core-hours, and search-tree overhead could readily raise this into the \(600\)--\(2{,}000\) core-hour range. At a realistic \(0.04\)--\(0.10\) USD/core-hour, that is roughly \(25\)--\(200\) USD, before independent validation. [C: explicit cost estimate, not a completed benchmark.]

Even a complete \(n=15\) table would remain finite evidence. It cannot establish or refute a positive limiting minimum-degree density. No heavier run was attempted on this VM.

6. Bottom line

• The live page allowed work: OPEN, no claimed proof, no current worker.
• Classical primary sources confirm the \(\Omega(n^{1/3})\) lower bound.
• The Hajós lemma extends Simonovits's even-order bound to every sufficiently large order.
• Luo--Ma--Yang gives \(0.328n\); the May 2026 checked-note artifact claims the improved \(0.3n+o(n)\) ceiling.
• The exact small-order values through \(14\) are now independently reprocessed and reproducible, with the first degree-\(4\) core at order \(12\).
• The three consecutive degree-\(4\) seed orders give a closed-form Hajós construction for every \(n\ge56\).
• Nothing here supplies the uniform positive density or the \(o(n)\) upper bound required to close Erdős #1032.

PARTIAL: verified g(4..14)=(3,0,3,3,3,3,3,3,4,4,4), extended Simonovits's Omega(n^(1/3)) bound to every sufficiently large order by Hajós joins, and constructed delta>=4 examples for every n>=56; the linear-growth question remains open below (3/10+o(1))n.