Erdős Problem #917

Erdős Problem 917 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT.
Fix an integer $k\ge 4$. Call a graph $G$ $k$-critical (edge-critical) if $\chi(G)=k$ and for every edge $e\in E(G)$ we have $\chi(G-e)<k$. For $n\ge 1$ define \[ f_k(n):=\max\{|E(G)|: |V(G)|=n\ \text{and $G$ is $k$-critical}\}. \] The questions ask:

1. $Q1$ Is it true that $f_k(n)\gg_k n^2$?
2. $Q2$ Is it true that $f_6(n)\sim n^2/4$?
3. $Q3$ More generally, for $k\ge 6$, is it true that \[ f_k(n) \sim \frac12\Big(1-\frac{1}{\lfloor k/3\rfloor}\Big)n^2\ ?\]

QUICK LITERATURE/CONTEXT CHECK.
The problem text states several known results (Dirac's construction and bounds of Toft/Stiebitz/Luo--Ma--Yang). I will not import those papers; instead I will fully verify the explicit Dirac-type construction given in the problem text and extract concrete lower bounds from it.

ATTACK PLAN.
Construction track. Verify that the join of odd cycles gives $k$-critical graphs with quadratic edge count for $k$ divisible by $3$ (Dirac/Erdős construction). Generalize to $k=3t$.

Asymptotic track. The conjectured exact asymptotics $Q2--Q3$ are not resolved here; we instead record the explicit lower bound constructions.

WORK.
Phase 1: fast reality check (computation on the explicit construction). Let $m=2$ so the odd cycles are $C_5$. I constructed the graph obtained by taking two disjoint copies of $C_5$ and adding all edges between them (the Dirac construction). A brute-force backtracking coloring check gives $\chi=6$ and, for every edge $e$, $\chi(G-e)\le 5$ (so the graph is $6$-critical). For $m=1$ the construction is $K_6$, which is also $6$-critical.

Lemma 917.1 (Dirac construction for $k=6$ is edge-critical and dense). Fix $m\ge 1$ and let $A,B$ be disjoint vertex sets with $|A|=|B|=2m+1$. Let $G$ be the graph obtained by:

• adding edges of a cycle $C_{2m+1}$ on $A$,
• adding edges of a cycle $C_{2m+1}$ on $B$,
• adding all edges between $A$ and $B$ (i.e. making $(A,B)$ complete bipartite).

Then $|V(G)|=4m+2$, \[ |E(G)|=(2m+1)^2+2(2m+1)=4m^2+8m+3, \] and $G$ is $6$-critical.

Proof. Step 1: edge count. Each cycle contributes $2m+1$ edges, so internal edges total $2(2m+1)$. The complete bipartite part contributes $(2m+1)(2m+1)=(2m+1)^2$ edges. Summing gives $|E(G)|=(2m+1)^2+2(2m+1)=4m^2+8m+3$.

Step 2: $\chi(G)=6$. Each odd cycle $C_{2m+1}$ has chromatic number $3$, so $\chi(G)\ge 3$ on $A$ and on $B$. Because every vertex in $A$ is adjacent to every vertex in $B$, no color used on $A$ can be reused on $B$. Therefore any proper coloring uses at least $3+3=6$ colors, so $\chi(G)\ge 6$.

Conversely, a proper $6$-coloring exists: color the cycle on $A$ with colors $1,2,3$ and color the cycle on $B$ with colors $4,5,6$. Cross edges only connect vertices in different parts, so there is no color conflict. Thus $\chi(G)\le 6$, hence $\chi(G)=6$.

Step 3: deleting any edge reduces the chromatic number.

Case 3a: $e$ is an edge within $A$ (or within $B$). Removing an edge from an odd cycle breaks it into a path, which is bipartite and thus $2$-colorable. Concretely, $C_{2m+1}-e$ is a path on $2m+1$ vertices, hence has $\chi=2$. The other part is still an odd cycle with $\chi=3$. As above, cross edges force disjoint color sets between the parts, so \[ \chi(G-e) \le 2+3=5<6. \]

Case 3b: $e$ is a cross edge between $A$ and $B$. Write $e=uv$ with $u\in A$ and $v\in B$. I will exhibit a proper $5$-coloring of $G-e$.

First, 3-color the cycle on $A$ with colors $1,2,3$ in such a way that $u$ is the only vertex of color $1$. This is possible: label the vertices of $A$ cyclically as $u=a_0,a_1,\dots,a_{2m}$ and assign colors \[ \mathrm{col}(a_0)=1,\qquad \mathrm{col}(a_i)=\begin{cases}2 & i\text{ odd},\\ 3 & i\text{ even and }i\ge 2. \end{cases} \] One checks that adjacent vertices receive different colors and that color $1$ appears exactly once.

Second, 3-color the cycle on $B$ with colors $1,4,5$ in such a way that $v$ is the only vertex of color $1$ (use the same pattern with the palette $\{1,4,5\}$).

In $G-e$, the only missing cross adjacency is between $u$ and $v$. Every other pair $(a\in A, b\in B)$ remains adjacent. Since color $1$ appears only on $u$ in $A$ and only on $v$ in $B$, the only potential cross-part color conflict for color $1$ would be between $u$ and $v$, but that edge was deleted. All other colors are disjoint between parts. Hence this is a proper coloring of $G-e$ using the five colors $\{1,2,3,4,5\}$, so $\chi(G-e)\le 5<6$.

Since every edge falls into one of these cases, deleting any edge reduces the chromatic number below $6$, i.e. $G$ is $6$-critical. $\square$

Lemma 917.2 (generalisation to $k=3t$ by joining $t$ odd cycles). Fix integers $t\ge 2$ and $m\ge 1$. Let $G$ be the join of $t$ disjoint copies of the odd cycle $C_{2m+1}$ (i.e. take $t$ disjoint cycles and add all edges between any two distinct cycles). Then:

1. (a) $\chi(G)=3t$ and $G$ is $(3t)$-critical.
2. (b) Writing $n:=|V(G)|=t(2m+1)$, we have \[ |E(G)|=\frac12\Big(1-\frac{1}{t}\Big)n^2 + n. \]

Proof. Step 1: chromatic number. Each cycle has chromatic number $3$. Since every vertex in one cycle is adjacent to every vertex in another, the color sets used on distinct cycles must be disjoint. Hence $\chi(G)\ge 3t$. Conversely, 3-color each cycle and use disjoint color palettes for different cycles; this gives a proper $3t$-coloring. Thus $\chi(G)=3t$.

Step 2: edge count. There are $t$ cycles, each contributing $2m+1$ internal edges, for a total of $t(2m+1)=n$ internal edges. For cross edges: between each pair of distinct cycles (there are $\binom{t}{2}$ such pairs) we have a complete bipartite graph on $(2m+1,2m+1)$, contributing $(2m+1)^2$ edges per pair. Thus cross edges total $\binom{t}{2}(2m+1)^2$. Using $n=t(2m+1)$ gives \[ \binom{t}{2}(2m+1)^2 = \frac{t(t-1)}{2}\cdot \frac{n^2}{t^2}=\frac12\Big(1-\frac1t\Big)n^2, \] so $|E(G)|=n+\frac12(1-1/t)n^2$.

Step 3: edge-criticality. Let $e$ be an arbitrary edge.

Case 3a: $e$ is within one cycle. Removing $e$ makes that cycle a path (2-colorable) while all other cycles remain 3-colorable. Because join edges remain between all different parts, a proper coloring may be taken by using 2 colors on the broken cycle and 3 fresh colors on each of the other $t-1$ cycles, for a total of $2+3(t-1)=3t-1$ colors. Hence $\chi(G-e)\le 3t-1<3t$.

Case 3b: $e$ is between two cycles. Suppose $e=uv$ with $u$ in cycle $A$ and $v$ in cycle $B$, where $A\ne B$. Color every cycle other than $A$ and $B$ with its own disjoint palette of $3$ colors.

Now color $A$ with colors $1,2,3$ so that $u$ is the unique vertex of color $1$ (the same explicit pattern as in Lemma 917.1). Color $B$ with colors $1,4,5$ so that $v$ is the unique vertex of color $1$. Since the only missing adjacency between the parts $A$ and $B$ is the deleted edge $uv$, and color $1$ appears only at $u$ in $A$ and only at $v$ in $B$, there is no conflict. All other cycles use disjoint palettes, so there are no cross-cycle conflicts.

Counting colors: the pair $A,B$ uses $\{1,2,3,4,5\}$ (5 colors), and each of the remaining $t-2$ cycles uses 3 fresh colors, for a total of $5+3(t-2)=3t-1$ colors. Thus $\chi(G-e)\le 3t-1<3t$.

This holds for every edge $e$, so $G$ is $(3t)$-critical. $\square$

VERIFICATION.

• Lemma 917.1 and Lemma 917.2 give explicit colorings after edge deletion; no appeal to external theorems is needed.
• The "unique color" 3-coloring pattern of an odd cycle is checked by direct adjacency along the cyclic order.
• Computation for $m=1,2,3$ (two-cycle join) confirmed $\chi=6$ and edge-criticality for small sizes.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: explicit quadratic lower bounds for infinitely many $n$ via Lemma 917.2. In particular, when $k=3t$ and $n=t(2m+1)$, \[ f_k(n)\ge \frac12\Big(1-\frac{1}{t}\Big)n^2+n. \] For $k=6$ this recovers Dirac's construction (Lemma 917.1) with $|E|=4m^2+8m+3$ on $n=4m+2$ vertices, i.e. $|E|=n^2/4+n+\tfrac12$.

(ii) First gap (crisp): Determine whether, for each fixed $k\ge 4$, there is a constant $c_k>0$ such that $f_k(n)\ge c_k n^2$ for all sufficiently large $n$, and determine the true asymptotic constant(s) in $Q2$--$Q3$ (even for $k=6$).

(iii) Top 3 next moves:

1. Extend the explicit join construction to all large $n$ (not only those representable as a sum of $t$ odd cycle lengths) while preserving $k$-criticality, e.g. via a controlled criticality-preserving composition operation.
2. For $k=6$, attempt to prove an upper bound $f_6(n)\le (1/4+o(1))n^2$ or else construct $6$-critical graphs with density strictly exceeding $1/4$.
3. For general $k$, study whether the "join of color-critical pieces" paradigm is asymptotically optimal, and if not, identify a concrete local gadget that increases edge density while preserving edge-criticality.

(iv) Minimal counterexample structure (to the conjectured asymptotic for a given $k$): a sequence of $k$-critical graphs on $n$ vertices whose edge density exceeds the conjectured constant by a fixed $\varepsilon>0$ infinitely often (to disprove), or conversely an argument showing that any $k$-critical graph with near-extremal edge count must resemble a complete multipartite join of a bounded number of almost-3-chromatic blocks (to prove).

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.

FORMAL RESTATEMENT.
Fix an integer $k\ge 4$. Call a graph $G$ $k$-critical (edge-critical) if $\chi(G)=k$ and for every edge $e\in E(G)$ we have $\chi(G-e)<k$. For $n\ge 1$ define \[ f_k(n):=\max\{|E(G)|: |V(G)|=n\ \text{and $G$ is $k$-critical}\}. \] The questions ask:

1. $Q1$ Is it true that $f_k(n)\gg_k n^2$?
2. $Q2$ Is it true that $f_6(n)\sim n^2/4$?
3. $Q3$ More generally, for $k\ge 6$, is it true that \[ f_k(n) \sim \frac12\Big(1-\frac{1}{\lfloor k/3\rfloor}\Big)n^2\ ?\]

QUICK LITERATURE/CONTEXT CHECK.
The problem text states several known results (Dirac's construction and bounds of Toft/Stiebitz/Luo--Ma--Yang). I will not import those papers; instead I will fully verify the explicit Dirac-type construction given in the problem text and extract concrete lower bounds from it.

ATTACK PLAN.
Construction track. Verify that the join of odd cycles gives $k$-critical graphs with quadratic edge count for $k$ divisible by $3$ (Dirac/Erdős construction). Generalize to $k=3t$.

Asymptotic track. The conjectured exact asymptotics $Q2--Q3$ are not resolved here; we instead record the explicit lower bound constructions.

WORK.
Phase 1: fast reality check (computation on the explicit construction). Let $m=2$ so the odd cycles are $C_5$. I constructed the graph obtained by taking two disjoint copies of $C_5$ and adding all edges between them (the Dirac construction). A brute-force backtracking coloring check gives $\chi=6$ and, for every edge $e$, $\chi(G-e)\le 5$ (so the graph is $6$-critical). For $m=1$ the construction is $K_6$, which is also $6$-critical.

Lemma 917.1 (Dirac construction for $k=6$ is edge-critical and dense). Fix $m\ge 1$ and let $A,B$ be disjoint vertex sets with $|A|=|B|=2m+1$. Let $G$ be the graph obtained by:

• adding edges of a cycle $C_{2m+1}$ on $A$,
• adding edges of a cycle $C_{2m+1}$ on $B$,
• adding all edges between $A$ and $B$ (i.e. making $(A,B)$ complete bipartite).

Then $|V(G)|=4m+2$, \[ |E(G)|=(2m+1)^2+2(2m+1)=4m^2+8m+3, \] and $G$ is $6$-critical.

Proof. Step 1: edge count. Each cycle contributes $2m+1$ edges, so internal edges total $2(2m+1)$. The complete bipartite part contributes $(2m+1)(2m+1)=(2m+1)^2$ edges. Summing gives $|E(G)|=(2m+1)^2+2(2m+1)=4m^2+8m+3$.

Step 2: $\chi(G)=6$. Each odd cycle $C_{2m+1}$ has chromatic number $3$, so $\chi(G)\ge 3$ on $A$ and on $B$. Because every vertex in $A$ is adjacent to every vertex in $B$, no color used on $A$ can be reused on $B$. Therefore any proper coloring uses at least $3+3=6$ colors, so $\chi(G)\ge 6$.

Conversely, a proper $6$-coloring exists: color the cycle on $A$ with colors $1,2,3$ and color the cycle on $B$ with colors $4,5,6$. Cross edges only connect vertices in different parts, so there is no color conflict. Thus $\chi(G)\le 6$, hence $\chi(G)=6$.

Step 3: deleting any edge reduces the chromatic number.

Case 3a: $e$ is an edge within $A$ (or within $B$). Removing an edge from an odd cycle breaks it into a path, which is bipartite and thus $2$-colorable. Concretely, $C_{2m+1}-e$ is a path on $2m+1$ vertices, hence has $\chi=2$. The other part is still an odd cycle with $\chi=3$. As above, cross edges force disjoint color sets between the parts, so \[ \chi(G-e) \le 2+3=5<6. \]

Case 3b: $e$ is a cross edge between $A$ and $B$. Write $e=uv$ with $u\in A$ and $v\in B$. I will exhibit a proper $5$-coloring of $G-e$.

First, 3-color the cycle on $A$ with colors $1,2,3$ in such a way that $u$ is the only vertex of color $1$. This is possible: label the vertices of $A$ cyclically as $u=a_0,a_1,\dots,a_{2m}$ and assign colors \[ \mathrm{col}(a_0)=1,\qquad \mathrm{col}(a_i)=\begin{cases}2 & i\text{ odd},\\ 3 & i\text{ even and }i\ge 2. \end{cases} \] One checks that adjacent vertices receive different colors and that color $1$ appears exactly once.

Second, 3-color the cycle on $B$ with colors $1,4,5$ in such a way that $v$ is the only vertex of color $1$ (use the same pattern with the palette $\{1,4,5\}$).

In $G-e$, the only missing cross adjacency is between $u$ and $v$. Every other pair $(a\in A, b\in B)$ remains adjacent. Since color $1$ appears only on $u$ in $A$ and only on $v$ in $B$, the only potential cross-part color conflict for color $1$ would be between $u$ and $v$, but that edge was deleted. All other colors are disjoint between parts. Hence this is a proper coloring of $G-e$ using the five colors $\{1,2,3,4,5\}$, so $\chi(G-e)\le 5<6$.

Since every edge falls into one of these cases, deleting any edge reduces the chromatic number below $6$, i.e. $G$ is $6$-critical. $\square$

Lemma 917.2 (generalisation to $k=3t$ by joining $t$ odd cycles). Fix integers $t\ge 2$ and $m\ge 1$. Let $G$ be the join of $t$ disjoint copies of the odd cycle $C_{2m+1}$ (i.e. take $t$ disjoint cycles and add all edges between any two distinct cycles). Then:

1. (a) $\chi(G)=3t$ and $G$ is $(3t)$-critical.
2. (b) Writing $n:=|V(G)|=t(2m+1)$, we have \[ |E(G)|=\frac12\Big(1-\frac{1}{t}\Big)n^2 + n. \]

Proof. Step 1: chromatic number. Each cycle has chromatic number $3$. Since every vertex in one cycle is adjacent to every vertex in another, the color sets used on distinct cycles must be disjoint. Hence $\chi(G)\ge 3t$. Conversely, 3-color each cycle and use disjoint color palettes for different cycles; this gives a proper $3t$-coloring. Thus $\chi(G)=3t$.

Step 2: edge count. There are $t$ cycles, each contributing $2m+1$ internal edges, for a total of $t(2m+1)=n$ internal edges. For cross edges: between each pair of distinct cycles (there are $\binom{t}{2}$ such pairs) we have a complete bipartite graph on $(2m+1,2m+1)$, contributing $(2m+1)^2$ edges per pair. Thus cross edges total $\binom{t}{2}(2m+1)^2$. Using $n=t(2m+1)$ gives \[ \binom{t}{2}(2m+1)^2 = \frac{t(t-1)}{2}\cdot \frac{n^2}{t^2}=\frac12\Big(1-\frac1t\Big)n^2, \] so $|E(G)|=n+\frac12(1-1/t)n^2$.

Step 3: edge-criticality. Let $e$ be an arbitrary edge.

Case 3a: $e$ is within one cycle. Removing $e$ makes that cycle a path (2-colorable) while all other cycles remain 3-colorable. Because join edges remain between all different parts, a proper coloring may be taken by using 2 colors on the broken cycle and 3 fresh colors on each of the other $t-1$ cycles, for a total of $2+3(t-1)=3t-1$ colors. Hence $\chi(G-e)\le 3t-1<3t$.

Case 3b: $e$ is between two cycles. Suppose $e=uv$ with $u$ in cycle $A$ and $v$ in cycle $B$, where $A\ne B$. Color every cycle other than $A$ and $B$ with its own disjoint palette of $3$ colors.

Now color $A$ with colors $1,2,3$ so that $u$ is the unique vertex of color $1$ (the same explicit pattern as in Lemma 917.1). Color $B$ with colors $1,4,5$ so that $v$ is the unique vertex of color $1$. Since the only missing adjacency between the parts $A$ and $B$ is the deleted edge $uv$, and color $1$ appears only at $u$ in $A$ and only at $v$ in $B$, there is no conflict. All other cycles use disjoint palettes, so there are no cross-cycle conflicts.

Counting colors: the pair $A,B$ uses $\{1,2,3,4,5\}$ (5 colors), and each of the remaining $t-2$ cycles uses 3 fresh colors, for a total of $5+3(t-2)=3t-1$ colors. Thus $\chi(G-e)\le 3t-1<3t$.

This holds for every edge $e$, so $G$ is $(3t)$-critical. $\square$

VERIFICATION.

• Lemma 917.1 and Lemma 917.2 give explicit colorings after edge deletion; no appeal to external theorems is needed.
• The "unique color" 3-coloring pattern of an odd cycle is checked by direct adjacency along the cyclic order.
• Computation for $m=1,2,3$ (two-cycle join) confirmed $\chi=6$ and edge-criticality for small sizes.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: explicit quadratic lower bounds for infinitely many $n$ via Lemma 917.2. In particular, when $k=3t$ and $n=t(2m+1)$, \[ f_k(n)\ge \frac12\Big(1-\frac{1}{t}\Big)n^2+n. \] For $k=6$ this recovers Dirac's construction (Lemma 917.1) with $|E|=4m^2+8m+3$ on $n=4m+2$ vertices, i.e. $|E|=n^2/4+n+\tfrac12$.

(ii) First gap (crisp): Determine whether, for each fixed $k\ge 4$, there is a constant $c_k>0$ such that $f_k(n)\ge c_k n^2$ for all sufficiently large $n$, and determine the true asymptotic constant(s) in $Q2$--$Q3$ (even for $k=6$).

(iii) Top 3 next moves:

1. Extend the explicit join construction to all large $n$ (not only those representable as a sum of $t$ odd cycle lengths) while preserving $k$-criticality, e.g. via a controlled criticality-preserving composition operation.
2. For $k=6$, attempt to prove an upper bound $f_6(n)\le (1/4+o(1))n^2$ or else construct $6$-critical graphs with density strictly exceeding $1/4$.
3. For general $k$, study whether the "join of color-critical pieces" paradigm is asymptotically optimal, and if not, identify a concrete local gadget that increases edge density while preserving edge-criticality.

(iv) Minimal counterexample structure (to the conjectured asymptotic for a given $k$): a sequence of $k$-critical graphs on $n$ vertices whose edge density exceeds the conjectured constant by a fixed $\varepsilon>0$ infinitely often (to disprove), or conversely an argument showing that any $k$-critical graph with near-extremal edge count must resemble a complete multipartite join of a bounded number of almost-3-chromatic blocks (to prove).