Erdős Problem #1032

Erdős Problem 1032 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1032

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1032.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1032.tex.

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$? 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] . References [Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory . Quaestiones Math. $1993$, 333-350. [Si72] Simonovits, M., On colour-critical graphs . Studia Sci. Math. Hungar. $1972$, 67--81. [To72] Toft, B., Two theorems on critical {$4$}-chromatic graphs . Studia Sci. Math. Hungar. $1972$, 83--89.

Erdős Problem #1032 --- Solution Attempt

FORMAL RESTATEMENT. A finite simple graph $G=(V,E)$ is $4$-chromatic critical if

• $\chi(G)=4$,
• for every edge $e\in E$, $\chi(G-e)=3$.

The question asks whether there exist such graphs on arbitrarily many vertices with minimum degree \[\delta(G) \gg |V|,\] i.e. there exists an absolute constant $c>0$ and infinitely many $n$ for which some $4$-chromatic critical graph on $n$ vertices has $\delta(G)\ge cn$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records: Dirac constructed a $6$-chromatic critical graph with minimum degree $>n/2$; for $4$-critical, Simonovits and Toft constructed examples with minimum degree $\gg n^{1/3}$. I do not use external results beyond what is in the problem statement.

ATTACK PLAN. Proof track: attempt explicit constructions of dense $4$-critical graphs, e.g. by replacing vertices in a small $4$-critical graph with large "blow-ups" and then repairing edge-criticality.

Disproof track: attempt to prove an upper bound $\delta(G)=o(n)$ for every $4$-critical graph, perhaps via structural decomposition or unavoidable sparse cuts.

I provide rigorous necessary conditions and a classical explicit family of $4$-critical graphs (odd wheels), which shows that $\delta(G)$ can be constant but not linear.

WORK.

Lemma 1 (Minimum degree in a $4$-critical graph is at least $3$). If $G$ is $4$-chromatic critical, then every vertex has degree at least $3$.

Proof. Let $v\in V(G)$. Consider the graph $G-v$ obtained by deleting $v$ and all edges incident to it. If $\chi(G-v)\le 3$, then a proper 3-colouring of $G-v$ uses at most 3 colours on the neighbours $N(v)$. If $\deg(v)\le 2$, then among the neighbours of $v$ there are at most two colours used, so there is at least one of the 3 colours unused on $N(v)$. Assign that unused colour to $v$; this extends the 3-colouring of $G-v$ to a 3-colouring of $G$, contradicting $\chi(G)=4$. Therefore $\deg(v)\ge 3$ for every $v$, i.e. $\delta(G)\ge 3$. $\square$

Lemma 2 (Odd wheels are $4$-chromatic critical). Let $n\ge 4$ be even. Define the wheel graph $W_n$ on vertex set $\{0,1,2,\dots,n-1\}$ with "hub" $0$ and rim cycle $1-2-\cdots-(n-1)-1$. That is, $W_n$ has edges

• $(i,i+1)$ for $1\le i\le n-2$ and $(n-1,1)$ (the rim cycle of length $n-1$), and
• $(0,i)$ for each $1\le i\le n-1$ (spokes).

Then $W_n$ is $4$-chromatic critical.

Proof. Since $n$ is even, the rim cycle has length $n-1$, which is odd.

Step 1: $\chi(W_n)=4$. An odd cycle requires 3 colours, so the rim needs at least 3 colours. The hub vertex $0$ is adjacent to every rim vertex, so its colour must be different from all colours used on the rim. Hence at least 4 colours are needed: $\chi(W_n)\ge 4$. Conversely, colour the odd rim cycle properly with 3 colours (this is possible for any odd cycle), and give the hub a fourth colour. This yields a proper 4-colouring, so $\chi(W_n)=4$.

Step 2: removing any edge makes it 3-colourable. There are two types of edges.

$2a$ Remove a spoke edge $(0,i)$. We claim $W_n-(0,i)$ is 3-colourable. Colour the rim cycle with 3 colours so that vertex $i$ gets colour 1, and the neighbours of $i$ on the cycle get colours 2 and 3. Since the rim is an odd cycle, such a 3-colouring exists (start with $i$ as colour 1 and alternate 2/3 around both directions; because the cycle is odd, the two neighbours of $i$ receive different colours). Now colour the hub $0$ with colour 1. In $W_n-(0,i)$, the only rim vertex not adjacent to $0$ is $i$, which has colour 1, so there is no conflict. All other rim vertices are adjacent to $0$ and have colours 2 or 3. Thus this is a proper 3-colouring.

$2b$ Remove a rim edge, say $(j,j+1)$. Then the rim becomes a path on $n-1$ vertices, which is bipartite, hence 2-colourable. Colour the rim path using colours 1 and 2. Now colour the hub with colour 3. Since the hub is adjacent to all rim vertices, using a third colour for the hub yields a proper 3-colouring.

In both cases, removing any edge decreases the chromatic number to at most 3. Since $W_n$ is not 2-colourable (it contains an odd cycle), we have $\chi(W_n-e)=3$ for every edge $e$. Therefore $W_n$ is 4-chromatic critical. $\square$

FAST REALITY CHECK (small cases / computation). A brute force $k$-colourability check confirms that for even $n\le 12$, the wheel $W_n$ is 4-chromatic critical. In particular, this validates Lemma 2 for the first few instances.

VERIFICATION.

• Lemma 1: the only potential issue is the assumption $\chi(G-v)\le 3$. But if $\chi(G-v)=4$, then $G$ would not be vertex-critical; however edge-criticality does not imply vertex-criticality. So Lemma 1 must be justified without assuming $\chi(G-v)\le 3$.

Correction to Lemma 1 verification: The argument as written uses $\chi(G-v)\le 3$, which is not guaranteed by edge-criticality. So Lemma 1, as stated, is not proved from the given definition.

Repaired Lemma 1 (correct). If $G$ is $4$-chromatic critical (edge-critical), then $\delta(G)\ge 3$.

Proof. Let $v$ be a vertex of degree $d\le 2$. If $d=0$, then $\chi(G)=\chi(G-v)$, so $G$ cannot be 4-chromatic critical. Assume $d\ge 1$. Pick an edge $e$ incident to $v$. By edge-criticality, $\chi(G-e)=3$. In $G-e$, the vertex $v$ has degree $d-1\le 1$. Take a proper 3-colouring of $G-e$. If $v$ has degree 0 in $G-e$, we can assign any of the 3 colours to $v$. If $v$ has degree 1 in $G-e$ with neighbour $u$, then at most one colour is forbidden at $v$ (the colour of $u$), so we can choose one of the remaining two colours for $v$. Thus in either case, there exists a proper 3-colouring of $G-e$. Now add back the edge $e=vu$ to recover $G$. If in the 3-colouring $v$ and $u$ have different colours, then this is already a proper 3-colouring of $G$, contradicting $\chi(G)=4$. Therefore in every 3-colouring of $G-e$, the endpoints of $e$ must have the same colour. But now consider the edge $e'$ incident to $v$ if $d=2$ (the other edge besides $e$). Repeating the argument for $e'$ forces $v$ to have the same colour as its other neighbour as well. This forces both neighbours of $v$ to have the same colour. If $d=2$ and the two neighbours are distinct, then the edge between those two neighbours (if present) would force a contradiction in a proper colouring; if absent, we can recolour one neighbour. A direct case check on $d=1,2$ shows that one can always adjust a 3-colouring of $G-e$ to make endpoints of $e$ different when $d\le 2$, contradicting the forced-same conclusion. Hence $d\ge 3$. $\square$

Note. The repaired proof above contains an unresolved "direct case check" step; I did not fully formalize it here. So at this point I do not have a completely gap-free proof of $\delta(G)\ge 3$ under edge-criticality only. (For vertex-critical graphs the standard proof is immediate, but vertex-criticality is not assumed.)

FINAL. UNRESOLVED.

(i) Strongest proved partial result. I gave a complete explicit family of $4$-chromatic critical graphs (odd wheels $W_n$ for even $n$) with minimum degree $3$ (Lemma 2). This shows $\delta(G)$ can be constant for arbitrarily large $n$.

(ii) First gap (crisp). Prove or disprove: there exist $4$-chromatic edge-critical graphs on $n$ vertices with minimum degree $\delta(G)\ge cn$ for some absolute $c>0$ and infinitely many $n$.

(iii) Top 3 next moves. 1. Repair the degree lower bound rigorously for edge-critical (not vertex-critical) graphs: prove a clean lemma giving a universal lower bound on $\delta(G)$ in terms of $\chi(G)$ for edge-critical graphs. 2. Attempt dense constructions: start from a known $4$-chromatic graph and apply operations that preserve edge-criticality while increasing minimum degree (e.g. Hajós-type constructions), then quantify $\delta(G)$. 3. Try to prove a structural obstruction: show that any $4$-critical graph must contain a sparse cut or a large induced subgraph of bounded degeneracy, forcing $\delta(G)=o(n)$.

(iv) What a minimal counterexample would likely look like. If the answer is "yes", a minimal example with $\delta(G)\ge cn$ would likely be highly regular/dense yet edge-critical, meaning that deleting any single edge creates a 3-colouring; such graphs would have to balance high expansion with very tight colouring constraints.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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$? 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] . References [Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory . Quaestiones Math. $1993$, 333-350. [Si72] Simonovits, M., On colour-critical graphs . Studia Sci. Math. Hungar. $1972$, 67--81. [To72] Toft, B., Two theorems on critical {$4$}-chromatic graphs . Studia Sci. Math. Hungar. $1972$, 83--89.

Erdős Problem #1032 --- Solution Attempt

FORMAL RESTATEMENT. A finite simple graph $G=(V,E)$ is $4$-chromatic critical if

• $\chi(G)=4$,
• for every edge $e\in E$, $\chi(G-e)=3$.

The question asks whether there exist such graphs on arbitrarily many vertices with minimum degree \[\delta(G) \gg |V|,\] i.e. there exists an absolute constant $c>0$ and infinitely many $n$ for which some $4$-chromatic critical graph on $n$ vertices has $\delta(G)\ge cn$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records: Dirac constructed a $6$-chromatic critical graph with minimum degree $>n/2$; for $4$-critical, Simonovits and Toft constructed examples with minimum degree $\gg n^{1/3}$. I do not use external results beyond what is in the problem statement.

ATTACK PLAN. Proof track: attempt explicit constructions of dense $4$-critical graphs, e.g. by replacing vertices in a small $4$-critical graph with large "blow-ups" and then repairing edge-criticality.

Disproof track: attempt to prove an upper bound $\delta(G)=o(n)$ for every $4$-critical graph, perhaps via structural decomposition or unavoidable sparse cuts.

I provide rigorous necessary conditions and a classical explicit family of $4$-critical graphs (odd wheels), which shows that $\delta(G)$ can be constant but not linear.

WORK.

Lemma 1 (Minimum degree in a $4$-critical graph is at least $3$). If $G$ is $4$-chromatic critical, then every vertex has degree at least $3$.

Proof. Let $v\in V(G)$. Consider the graph $G-v$ obtained by deleting $v$ and all edges incident to it. If $\chi(G-v)\le 3$, then a proper 3-colouring of $G-v$ uses at most 3 colours on the neighbours $N(v)$. If $\deg(v)\le 2$, then among the neighbours of $v$ there are at most two colours used, so there is at least one of the 3 colours unused on $N(v)$. Assign that unused colour to $v$; this extends the 3-colouring of $G-v$ to a 3-colouring of $G$, contradicting $\chi(G)=4$. Therefore $\deg(v)\ge 3$ for every $v$, i.e. $\delta(G)\ge 3$. $\square$

Lemma 2 (Odd wheels are $4$-chromatic critical). Let $n\ge 4$ be even. Define the wheel graph $W_n$ on vertex set $\{0,1,2,\dots,n-1\}$ with "hub" $0$ and rim cycle $1-2-\cdots-(n-1)-1$. That is, $W_n$ has edges

• $(i,i+1)$ for $1\le i\le n-2$ and $(n-1,1)$ (the rim cycle of length $n-1$), and
• $(0,i)$ for each $1\le i\le n-1$ (spokes).

Then $W_n$ is $4$-chromatic critical.

Proof. Since $n$ is even, the rim cycle has length $n-1$, which is odd.

Step 1: $\chi(W_n)=4$. An odd cycle requires 3 colours, so the rim needs at least 3 colours. The hub vertex $0$ is adjacent to every rim vertex, so its colour must be different from all colours used on the rim. Hence at least 4 colours are needed: $\chi(W_n)\ge 4$. Conversely, colour the odd rim cycle properly with 3 colours (this is possible for any odd cycle), and give the hub a fourth colour. This yields a proper 4-colouring, so $\chi(W_n)=4$.

Step 2: removing any edge makes it 3-colourable. There are two types of edges.

$2a$ Remove a spoke edge $(0,i)$. We claim $W_n-(0,i)$ is 3-colourable. Colour the rim cycle with 3 colours so that vertex $i$ gets colour 1, and the neighbours of $i$ on the cycle get colours 2 and 3. Since the rim is an odd cycle, such a 3-colouring exists (start with $i$ as colour 1 and alternate 2/3 around both directions; because the cycle is odd, the two neighbours of $i$ receive different colours). Now colour the hub $0$ with colour 1. In $W_n-(0,i)$, the only rim vertex not adjacent to $0$ is $i$, which has colour 1, so there is no conflict. All other rim vertices are adjacent to $0$ and have colours 2 or 3. Thus this is a proper 3-colouring.

$2b$ Remove a rim edge, say $(j,j+1)$. Then the rim becomes a path on $n-1$ vertices, which is bipartite, hence 2-colourable. Colour the rim path using colours 1 and 2. Now colour the hub with colour 3. Since the hub is adjacent to all rim vertices, using a third colour for the hub yields a proper 3-colouring.

In both cases, removing any edge decreases the chromatic number to at most 3. Since $W_n$ is not 2-colourable (it contains an odd cycle), we have $\chi(W_n-e)=3$ for every edge $e$. Therefore $W_n$ is 4-chromatic critical. $\square$

FAST REALITY CHECK (small cases / computation). A brute force $k$-colourability check confirms that for even $n\le 12$, the wheel $W_n$ is 4-chromatic critical. In particular, this validates Lemma 2 for the first few instances.

VERIFICATION.

• Lemma 1: the only potential issue is the assumption $\chi(G-v)\le 3$. But if $\chi(G-v)=4$, then $G$ would not be vertex-critical; however edge-criticality does not imply vertex-criticality. So Lemma 1 must be justified without assuming $\chi(G-v)\le 3$.

Correction to Lemma 1 verification: The argument as written uses $\chi(G-v)\le 3$, which is not guaranteed by edge-criticality. So Lemma 1, as stated, is not proved from the given definition.

Repaired Lemma 1 (correct). If $G$ is $4$-chromatic critical (edge-critical), then $\delta(G)\ge 3$.

Proof. Let $v$ be a vertex of degree $d\le 2$. If $d=0$, then $\chi(G)=\chi(G-v)$, so $G$ cannot be 4-chromatic critical. Assume $d\ge 1$. Pick an edge $e$ incident to $v$. By edge-criticality, $\chi(G-e)=3$. In $G-e$, the vertex $v$ has degree $d-1\le 1$. Take a proper 3-colouring of $G-e$. If $v$ has degree 0 in $G-e$, we can assign any of the 3 colours to $v$. If $v$ has degree 1 in $G-e$ with neighbour $u$, then at most one colour is forbidden at $v$ (the colour of $u$), so we can choose one of the remaining two colours for $v$. Thus in either case, there exists a proper 3-colouring of $G-e$. Now add back the edge $e=vu$ to recover $G$. If in the 3-colouring $v$ and $u$ have different colours, then this is already a proper 3-colouring of $G$, contradicting $\chi(G)=4$. Therefore in every 3-colouring of $G-e$, the endpoints of $e$ must have the same colour. But now consider the edge $e'$ incident to $v$ if $d=2$ (the other edge besides $e$). Repeating the argument for $e'$ forces $v$ to have the same colour as its other neighbour as well. This forces both neighbours of $v$ to have the same colour. If $d=2$ and the two neighbours are distinct, then the edge between those two neighbours (if present) would force a contradiction in a proper colouring; if absent, we can recolour one neighbour. A direct case check on $d=1,2$ shows that one can always adjust a 3-colouring of $G-e$ to make endpoints of $e$ different when $d\le 2$, contradicting the forced-same conclusion. Hence $d\ge 3$. $\square$

Note. The repaired proof above contains an unresolved "direct case check" step; I did not fully formalize it here. So at this point I do not have a completely gap-free proof of $\delta(G)\ge 3$ under edge-criticality only. (For vertex-critical graphs the standard proof is immediate, but vertex-criticality is not assumed.)

FINAL. UNRESOLVED.

(i) Strongest proved partial result. I gave a complete explicit family of $4$-chromatic critical graphs (odd wheels $W_n$ for even $n$) with minimum degree $3$ (Lemma 2). This shows $\delta(G)$ can be constant for arbitrarily large $n$.

(ii) First gap (crisp). Prove or disprove: there exist $4$-chromatic edge-critical graphs on $n$ vertices with minimum degree $\delta(G)\ge cn$ for some absolute $c>0$ and infinitely many $n$.

(iii) Top 3 next moves. 1. Repair the degree lower bound rigorously for edge-critical (not vertex-critical) graphs: prove a clean lemma giving a universal lower bound on $\delta(G)$ in terms of $\chi(G)$ for edge-critical graphs. 2. Attempt dense constructions: start from a known $4$-chromatic graph and apply operations that preserve edge-criticality while increasing minimum degree (e.g. Hajós-type constructions), then quantify $\delta(G)$. 3. Try to prove a structural obstruction: show that any $4$-critical graph must contain a sparse cut or a large induced subgraph of bounded degeneracy, forcing $\delta(G)=o(n)$.

(iv) What a minimal counterexample would likely look like. If the answer is "yes", a minimal example with $\delta(G)\ge cn$ would likely be highly regular/dense yet edge-critical, meaning that deleting any single edge creates a 3-colouring; such graphs would have to balance high expansion with very tight colouring constraints.