Erdős Problem #944

Erdős Problem 944 --- collection record

PROVENANCE AND STATUS

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

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/944.tex.

REUSED SOURCE 1

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

A critical vertex, edge, or set of edges, 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$? A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical. This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open. Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$. Skottova and Steiner [SkSt25] have improved this, proving that such graphs exist for all $k\geq 5$ and $r\geq 1$. The only remaining open case is $k=4$ (even the case $k=4$ and $r=1$ remains open). Erdős also asked a stronger quantitative form of this question: let $f_k(n)$ denote the largest $r\geq 1$ such that there exists a $k$-vertex-critical graph on $n$ vertices such that no set of at most $r$ edges is critical. He then asks whether $f_k(n)\to \infty$ as $n\to \infty$. Skottova and Steiner [SkSt25] have proved this for $k\geq 5$, establishing the bounds\[n^{1/3}\ll_k f_k(n) \ll_k \frac{n}{(\log n)^C}\]for all $k\geq 5$, where $C>0$ is an absolute constant. This is Problem 91 in the graph problems collection. See also [917] and [1032] . References [Br92] Brown, Jason I., A vertex critical graph without critical edges . Discrete Math. $1992$, 99--101. [Je02] Jensen, Tommy R., Dense critical and vertex-critical graphs . Discrete Math. $2002$, 63--84. [La02] Lattanzio, John J., A note on a conjecture of {D}irac . Discrete Math. $2002$, 323--330. [MaSt25] Martinsson, Anders and Steiner, Raphael, Vertex-critical graphs far from edge-criticality . Combin. Probab. Comput. $2025$, 151--157. [SkSt25] E. Skottova and R. Steiner, Critical edge sets in vertex-critical graphs . arXiv:2508.08703 $2025$.

FORMAL RESTATEMENT

All graphs here are finite, simple, undirected. For a graph $G$, let $\chi(G)$ be its chromatic number. A vertex $v$ is critical if $\chi(G-v)<\chi(G)$. An edge set $F\subseteq E(G)$ is critical if $\chi(G-F)<\chi(G)$. Fix integers $k\ge 4$ and $r\ge 1$. Question: Does there exist a graph $G$ such that

1. $\chi(G)=k$,
2. every vertex is critical (equivalently, $G$ is $k$-vertex-critical), and
3. every critical edge set $F$ has size $|F|>r$?

A quantitative variant defines $f_k(n)$ as the largest $r$ such that there exists a $k$-vertex-critical graph $G$ on $n$ vertices with no critical edge set of size $\le r$, and asks whether $f_k(n)\to\infty$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The problem text states that for $k\ge 5$ and any $r\ge 1$, such graphs exist, and that $k=4$ remains the only open case (including $r=1$).

ATTACK PLAN

Proof-track ideas (for $k=4$).

• Derive necessary structural constraints for a hypothetical $4$-vertex-critical graph with no small critical edge sets (connectivity, minimum degree, edge cuts), then attempt to show those constraints are incompatible.
• Try to adapt known $k\ge 5$ constructions (mentioned in the text) down to $k=4$ by replacing gadgets and maintaining $4$-criticality.

Disproof-track ideas.

• For $k=4$, attempt to show every $4$-vertex-critical graph has a critical edge (Dirac's conjecture at $(k,r)=(4,1)$); even a proof for restricted families (planar, triangle-free, bounded degree) would be progress.
• Computational search in known families (wheels, Mycielski graphs, Hajós joins) to see whether critical edges persist.

WORK

Fast reality check (explicit computation on standard families).

Using a brute-force exact chromatic-number checker (backtracking) I verified:

• $K_4$ is $4$-vertex-critical and has critical edges (indeed every edge is critical).
• Odd wheels $W_n$ (wheel on $n$ vertices with $n-1$ an odd cycle, i.e. $n$ even) are $4$-chromatic and $4$-vertex-critical for $n\in\{6,8,10,12\}$; each has a critical edge (minimum critical edge-set size $=1$).
• The Mycielski graph of $C_5$ (11 vertices, 4-chromatic and triangle-free) is $4$-vertex-critical and has a critical edge (minimum critical edge-set size $=1$).

These checks only test a few explicit families; they do not address the open case.

Lemma 944.1 (minimum degree in $k$-vertex-critical graphs).

If $G$ is $k$-vertex-critical (i.e. $\chi(G)=k$ and $\chi(G-v)=k-1$ for all $v\in V(G)$), then \[ \delta(G)\ge k-1. \]

Proof. Assume for contradiction that $G$ has a vertex $v$ with degree $d(v)\le k-2$. Since $G$ is $k$-vertex-critical, $G-v$ is $(k-1)$-colorable; fix a proper coloring of $G-v$ with colors $\{1,\dots,k-1\}$. The neighbors of $v$ use at most $d(v)\le k-2$ colors among these $k-1$ colors, so there exists a color $c\in\{1,\dots,k-1\}$ not used on $N(v)$. Assign color $c$ to $v$. This extends the coloring to a proper $(k-1)$-coloring of $G$, contradicting $\chi(G)=k$. $\Box$

Lemma 944.2 ($k$-vertex-critical graphs are 2-connected).

If $G$ is $k$-vertex-critical, then $G$ has no cut-vertex (i.e. $G$ is 2-connected).

Proof. Assume for contradiction that $v$ is a cut-vertex. Then $G-v$ has at least two connected components; pick a partition of $V(G)\setminus\{v\}$ into nonempty sets $A,B$ such that there are no edges between $A$ and $B$ in $G-v$. Let $G_A$ be the induced subgraph on $A\cup\{v\}$ and $G_B$ the induced subgraph on $B\cup\{v\}$.

Claim: $\chi(G_A)\le k-1$ and $\chi(G_B)\le k-1$. Indeed, if $\chi(G_A)=k$, then for any $x\in B$ the graph $G-x$ still contains $G_A$ as a subgraph, so $\chi(G-x)\ge \chi(G_A)=k$. This contradicts $k$-vertex-criticality, which gives $\chi(G-x)=k-1$. The same argument applies to $G_B$.

Now fix proper $(k-1)$-colorings $\varphi_A$ of $G_A$ and $\varphi_B$ of $G_B$. Let the color of $v$ under $\varphi_A$ be $c_A\in\{1,\dots,k-1\}$ and under $\varphi_B$ be $c_B$. If $c_A\ne c_B$, permute the color names in $\varphi_B$ by a bijection of $\{1,\dots,k-1\}$ sending $c_B$ to $c_A$; this yields another proper coloring of $G_B$ in which $v$ has color $c_A$. Now the two colorings agree on $v$, so together they define a proper $(k-1)$-coloring of all of $G$ (there are no edges between $A$ and $B$). This contradicts $\chi(G)=k$. $\Box$

VERIFICATION

• Lemma 944.1: checked that the extension step is valid because only neighbors of $v$ can conflict with $v$'s color.
• Lemma 944.2: checked the key claim: if a subgraph has chromatic number $k$, deleting a vertex outside that subgraph cannot reduce its chromatic number, so the whole graph still needs $k$ colors.
• Computation sanity: For $K_4$, deleting any edge yields a graph with a $K_3$ plus a pendant vertex adjacent to two vertices, which is 3-colorable; hence each edge is critical.

FINAL

UNRESOLVED (i) Strongest proved partial result: any $k$-vertex-critical graph must satisfy $\delta(G)\ge k-1$ (Lemma 944.1) and be 2-connected (Lemma 944.2). Computations show that standard $4$-vertex-critical families (odd wheels, Mycielski$C5$) do have critical edges. (ii) First gap: resolve the $k=4$ case, even for $r=1$: either construct a $4$-vertex-critical graph with no critical edge, or prove every $4$-vertex-critical graph has a critical edge. (iii) Top 3 next moves:

1. Prove additional necessary structure for a minimal counterexample at $k=4$ (e.g. 3-connectedness, constraints on edge cuts, reducible configurations), then attempt a discharging-style contradiction.
2. Run a targeted computer search in families known to generate all $4$-critical graphs up to a given size (e.g. via Ore/Hajós constructions) and record whether any lacks critical edges.
3. Examine whether $k\ge 5$ constructions from the problem text can be modified to lower chromatic number while preserving the "far from edge-critical" property.

(iv) Minimal counterexample structure: a $4$-vertex-critical graph with no critical edge set of size $\le r$ would likely need to be highly connected (at least 2-connected by Lemma 944.2), with minimum degree at least 3 (Lemma 944.1), and to avoid all obvious reducible gadgets (wheels/Mycielski-type constructions) that introduce critical edges.

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.

A critical vertex, edge, or set of edges, 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$? A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical. This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open. Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$. Skottova and Steiner [SkSt25] have improved this, proving that such graphs exist for all $k\geq 5$ and $r\geq 1$. The only remaining open case is $k=4$ (even the case $k=4$ and $r=1$ remains open). Erdős also asked a stronger quantitative form of this question: let $f_k(n)$ denote the largest $r\geq 1$ such that there exists a $k$-vertex-critical graph on $n$ vertices such that no set of at most $r$ edges is critical. He then asks whether $f_k(n)\to \infty$ as $n\to \infty$. Skottova and Steiner [SkSt25] have proved this for $k\geq 5$, establishing the bounds\[n^{1/3}\ll_k f_k(n) \ll_k \frac{n}{(\log n)^C}\]for all $k\geq 5$, where $C>0$ is an absolute constant. This is Problem 91 in the graph problems collection. See also [917] and [1032] . References [Br92] Brown, Jason I., A vertex critical graph without critical edges . Discrete Math. $1992$, 99--101. [Je02] Jensen, Tommy R., Dense critical and vertex-critical graphs . Discrete Math. $2002$, 63--84. [La02] Lattanzio, John J., A note on a conjecture of {D}irac . Discrete Math. $2002$, 323--330. [MaSt25] Martinsson, Anders and Steiner, Raphael, Vertex-critical graphs far from edge-criticality . Combin. Probab. Comput. $2025$, 151--157. [SkSt25] E. Skottova and R. Steiner, Critical edge sets in vertex-critical graphs . arXiv:2508.08703 $2025$.

FORMAL RESTATEMENT

All graphs here are finite, simple, undirected. For a graph $G$, let $\chi(G)$ be its chromatic number. A vertex $v$ is critical if $\chi(G-v)<\chi(G)$. An edge set $F\subseteq E(G)$ is critical if $\chi(G-F)<\chi(G)$. Fix integers $k\ge 4$ and $r\ge 1$. Question: Does there exist a graph $G$ such that

1. $\chi(G)=k$,
2. every vertex is critical (equivalently, $G$ is $k$-vertex-critical), and
3. every critical edge set $F$ has size $|F|>r$?

A quantitative variant defines $f_k(n)$ as the largest $r$ such that there exists a $k$-vertex-critical graph $G$ on $n$ vertices with no critical edge set of size $\le r$, and asks whether $f_k(n)\to\infty$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The problem text states that for $k\ge 5$ and any $r\ge 1$, such graphs exist, and that $k=4$ remains the only open case (including $r=1$).

ATTACK PLAN

Proof-track ideas (for $k=4$).

• Derive necessary structural constraints for a hypothetical $4$-vertex-critical graph with no small critical edge sets (connectivity, minimum degree, edge cuts), then attempt to show those constraints are incompatible.
• Try to adapt known $k\ge 5$ constructions (mentioned in the text) down to $k=4$ by replacing gadgets and maintaining $4$-criticality.

Disproof-track ideas.

• For $k=4$, attempt to show every $4$-vertex-critical graph has a critical edge (Dirac's conjecture at $(k,r)=(4,1)$); even a proof for restricted families (planar, triangle-free, bounded degree) would be progress.
• Computational search in known families (wheels, Mycielski graphs, Hajós joins) to see whether critical edges persist.

WORK

Fast reality check (explicit computation on standard families).

Using a brute-force exact chromatic-number checker (backtracking) I verified:

• $K_4$ is $4$-vertex-critical and has critical edges (indeed every edge is critical).
• Odd wheels $W_n$ (wheel on $n$ vertices with $n-1$ an odd cycle, i.e. $n$ even) are $4$-chromatic and $4$-vertex-critical for $n\in\{6,8,10,12\}$; each has a critical edge (minimum critical edge-set size $=1$).
• The Mycielski graph of $C_5$ (11 vertices, 4-chromatic and triangle-free) is $4$-vertex-critical and has a critical edge (minimum critical edge-set size $=1$).

These checks only test a few explicit families; they do not address the open case.

Lemma 944.1 (minimum degree in $k$-vertex-critical graphs).

If $G$ is $k$-vertex-critical (i.e. $\chi(G)=k$ and $\chi(G-v)=k-1$ for all $v\in V(G)$), then \[ \delta(G)\ge k-1. \]

Proof. Assume for contradiction that $G$ has a vertex $v$ with degree $d(v)\le k-2$. Since $G$ is $k$-vertex-critical, $G-v$ is $(k-1)$-colorable; fix a proper coloring of $G-v$ with colors $\{1,\dots,k-1\}$. The neighbors of $v$ use at most $d(v)\le k-2$ colors among these $k-1$ colors, so there exists a color $c\in\{1,\dots,k-1\}$ not used on $N(v)$. Assign color $c$ to $v$. This extends the coloring to a proper $(k-1)$-coloring of $G$, contradicting $\chi(G)=k$. $\Box$

Lemma 944.2 ($k$-vertex-critical graphs are 2-connected).

If $G$ is $k$-vertex-critical, then $G$ has no cut-vertex (i.e. $G$ is 2-connected).

Proof. Assume for contradiction that $v$ is a cut-vertex. Then $G-v$ has at least two connected components; pick a partition of $V(G)\setminus\{v\}$ into nonempty sets $A,B$ such that there are no edges between $A$ and $B$ in $G-v$. Let $G_A$ be the induced subgraph on $A\cup\{v\}$ and $G_B$ the induced subgraph on $B\cup\{v\}$.

Claim: $\chi(G_A)\le k-1$ and $\chi(G_B)\le k-1$. Indeed, if $\chi(G_A)=k$, then for any $x\in B$ the graph $G-x$ still contains $G_A$ as a subgraph, so $\chi(G-x)\ge \chi(G_A)=k$. This contradicts $k$-vertex-criticality, which gives $\chi(G-x)=k-1$. The same argument applies to $G_B$.

Now fix proper $(k-1)$-colorings $\varphi_A$ of $G_A$ and $\varphi_B$ of $G_B$. Let the color of $v$ under $\varphi_A$ be $c_A\in\{1,\dots,k-1\}$ and under $\varphi_B$ be $c_B$. If $c_A\ne c_B$, permute the color names in $\varphi_B$ by a bijection of $\{1,\dots,k-1\}$ sending $c_B$ to $c_A$; this yields another proper coloring of $G_B$ in which $v$ has color $c_A$. Now the two colorings agree on $v$, so together they define a proper $(k-1)$-coloring of all of $G$ (there are no edges between $A$ and $B$). This contradicts $\chi(G)=k$. $\Box$

VERIFICATION

• Lemma 944.1: checked that the extension step is valid because only neighbors of $v$ can conflict with $v$'s color.
• Lemma 944.2: checked the key claim: if a subgraph has chromatic number $k$, deleting a vertex outside that subgraph cannot reduce its chromatic number, so the whole graph still needs $k$ colors.
• Computation sanity: For $K_4$, deleting any edge yields a graph with a $K_3$ plus a pendant vertex adjacent to two vertices, which is 3-colorable; hence each edge is critical.

FINAL

UNRESOLVED (i) Strongest proved partial result: any $k$-vertex-critical graph must satisfy $\delta(G)\ge k-1$ (Lemma 944.1) and be 2-connected (Lemma 944.2). Computations show that standard $4$-vertex-critical families (odd wheels, Mycielski$C5$) do have critical edges. (ii) First gap: resolve the $k=4$ case, even for $r=1$: either construct a $4$-vertex-critical graph with no critical edge, or prove every $4$-vertex-critical graph has a critical edge. (iii) Top 3 next moves:

1. Prove additional necessary structure for a minimal counterexample at $k=4$ (e.g. 3-connectedness, constraints on edge cuts, reducible configurations), then attempt a discharging-style contradiction.
2. Run a targeted computer search in families known to generate all $4$-critical graphs up to a given size (e.g. via Ore/Hajós constructions) and record whether any lacks critical edges.
3. Examine whether $k\ge 5$ constructions from the problem text can be modified to lower chromatic number while preserving the "far from edge-critical" property.

(iv) Minimal counterexample structure: a $4$-vertex-critical graph with no critical edge set of size $\le r$ would likely need to be highly connected (at least 2-connected by Lemma 944.2), with minimum degree at least 3 (Lemma 944.1), and to avoid all obvious reducible gadgets (wheels/Mycielski-type constructions) that introduce critical edges.