Erdős Problem #108

Erdős Problem 108: high girth inside a high-chromatic host

Statement and scope

For fixed $k\ge2$ and $r\ge4$, must some $f(k,r)$ ensure that every graph of chromatic number at least $f(k,r)$ contains a subgraph of girth at least $r$ and chromatic number at least $k$? The universal-host assertion is unresolved here. We prove necessary size bounds, the case $k=2$, and the distinction between the required assertion and the classical existence of high-girth, high-chromatic graphs.

This revises the earlier GPT-5.2 attempt, retaining its valid critical-subgraph reduction and correcting its assertion that an entire breadth-first ball must be a tree. Source statement: https://www.erdosproblems.com/108. The random-graph existence argument below is the classical Erdős method; no novelty is claimed.

Critical graphs and the Moore obstruction

A finite graph with chromatic number at least $k$ has a vertex-minimal induced subgraph $H$ with this property. Deleting any vertex leaves a $(k-1)$-colourable graph, so $\chi(H)=k$ and every vertex of $H$ has degree at least $k-1$: otherwise its colour could be supplied after colouring the other vertices.

For minimum degree $d\ge2$ and girth at least $r$, breadth-first path counting gives \[ |H|\ge \begin{cases} 1+d\sum_{i=0}^{s-1}(d-1)^i,&r=2s+1,\\ 2\sum_{i=0}^{s-1}(d-1)^i,&r=2s. \end{cases} \tag{1} \] For odd $r$, root at a vertex and count nonbacktracking paths of lengths up to $s$. A repeated vertex, or two distinct such paths with the same endpoint, would create a cycle of length at most $2s$. Thus the path endpoints counted at each level are distinct. Edges between vertices of the last level may exist; they are not used or excluded by this argument.

For even $r$, root at an edge and grow paths to depth $s-1$ on each side, forbidding the root edge as the first step. A collision on one side gives a cycle of length at most $2s-2$, and a collision between the two sides gives one of length at most $2s-1$. This proves the second formula.

If a threshold $f(k,r)$ exists, apply its assertion to the complete graph on $f(k,r)$ vertices and then to a critical subgraph of the promised witness. For $k\ge3$, $1$ with $d=k-1$ is therefore a necessary lower bound on $f(k,r)$. For $k=2$, the exact threshold is $2$: every graph of chromatic number at least two contains an edge, whose girth is infinite.

Existence does not supply the universal host

For completeness, fix $k,r$ and let $G$ be a random graph on $N$ vertices with independent edge probability \[ p=N^{-1+1/(2r)}. \] The expected number of cycles of lengths $3,\ldots,r-1$ is at most $\sum_{\ell=3}^{r-1}(Np)^\ell/(2\ell)=O_r(N^{1/2})$. Markov's inequality shows that, with probability tending to one, fewer than $N/2$ such cycles occur.

Put $t=\lceil N/(2k)\rceil$. The expected number of independent $t$-sets is at most \[ {N\choose t}(1-p)^{\binom t2} \le 2^N\exp\left(-p\binom t2\right)=o(1), \] since $p t^2$ has order $N^{1+1/(2r)}$. Hence some graph has fewer than $N/2$ short cycles and no independent $t$-set. Remove at most one vertex for each short cycle. The remaining graph $H$ has more than $N/2$ vertices, girth at least $r$, and independence number at most $t-1<N/(2k)$. Consequently $\chi(H)\ge |H|/\alpha(H)>k$.

This constructs witnesses inside sufficiently large complete graphs. An arbitrary high-chromatic host need not contain those complete graphs, so the construction does not establish the requested extraction theorem.

Remaining gap

We have a quantitative necessary obstruction and witnesses for some hosts. A procedure that extracts a high-girth, high-chromatic subgraph from every sufficiently high-chromatic host is still missing.

COMPLETION ESTIMATE

COMPLETION: 30%

Erdős Problem #108

1) FORMAL RESTATEMENT

For integers $r\ge4$ and $k\ge2$, define $f(k,r)$ to be the least integer (if it exists) with the following property:

Every (finite) graph $G$ with $\chi(G)\ge f(k,r)$ contains a subgraph $H\subseteq G$ such that $\chi(H)\ge k$ and the girth $g(H)\ge r$.

Question: does such a finite $f(k,r)$ exist for every $r\ge4$ and $k\ge2$?

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:

• Rödl proved the case $r=4$.
• The "infinite version" is open.
• Erdős asked whether $\lim_{k\to\infty} f(k,r+1)/f(k,r)=\infty$.

No further literature is used here.

3) ATTACK PLAN

• Proof track: attempt to extract from $\chi(G)$ a $k$-chromatic subgraph with large minimum degree, then delete short cycles while preserving chromatic number; or apply probabilistic/iterative thinning.
• Disproof track: try to build graphs of arbitrarily large chromatic number in which every large-girth subgraph has bounded chromatic number.

I do not resolve existence of $f(k,r)$ here. I record two rigorous, problem-specific lemmas that constrain what $f(k,r)$ would have to look like.

4) WORK

Lemma 108.1 ($k$-critical subgraphs have minimum degree $\ge k-1$).

Let $G$ be a finite graph with $\chi(G)\ge k$. Then $G$ contains a subgraph $H\subseteq G$ with $\chi(H)=k$ such that every vertex of $H$ has degree at least $k-1$ within $H$.

Proof. Among all subgraphs of $G$ with chromatic number at least $k$, choose one with the minimum number of vertices; call it $H$. Then $\chi(H)\ge k$ by construction, and minimality forces $\chi(H)=k$ because if $\chi(H)\ge k+1$ we could potentially find a smaller subgraph still of chromatic $\ge k$ by deleting vertices, contradicting minimality (more directly: minimality already gives that deleting any vertex drops chromatic number below $k$, hence $\chi(H)=k$).

Now fix a vertex $v\in V(H)$ and consider $H-v$ (delete $v$ and incident edges). By minimality, $\chi(H-v)\le k-1$. Let $c:V(H)\setminus\{v\}\to\{1,\dots,k-1\}$ be a proper $(k-1)$-coloring of $H-v$.

If $\deg_H(v)\le k-2$, then among the $k-1$ colors there is at least one color not used on the neighbors of $v$ (pigeonhole principle). Assigning that unused color to $v$ extends $c$ to a proper $(k-1)$-coloring of all of $H$, contradicting $\chi(H)=k$. Therefore $\deg_H(v)\ge k-1$ for every $v$. $\square$

Lemma 108.2 (Moore-type lower bound from girth and minimum degree).

Let $H$ be a finite graph with minimum degree $\delta(H)\ge d\ge2$ and girth $g(H)\ge r$. Write $t:=\lfloor (r-1)/2\rfloor$. Then \[ |V(H)|\ge 1+d\sum_{i=0}^{t-1}(d-1)^i. \] In particular, $|V(H)|\ge 1+d((d-1)^t-1)/(d-2)$ if $d>2$.

Proof. Pick a root vertex $v$. Perform a breadth-first search (BFS) expansion. Because the girth is at least $r$, the BFS layers out to distance $t$ form a tree: there are no cycles of length $\le 2t+1\le r-1$ (if $r$ is odd) or $\le 2t\le r-2$ (if $r$ is even), so no edge can connect two vertices within the explored ball without creating a short cycle.

At distance $0$ there is $1$ vertex. At distance $1$, vertex $v$ has at least $d$ neighbors. Each vertex at distance $i\ge1$ has at least $d-1$ neighbors outside the previous layer (one neighbor is its parent in the BFS tree). Therefore the number of vertices at distance $i$ is at least $d(d-1)^{i-1}$ for $1\le i\le t$. Summing gives \[ |V(H)|\ge 1+\sum_{i=1}^t d(d-1)^{i-1} = 1+d\sum_{i=0}^{t-1}(d-1)^i. \] $\square$

Consequence 108.3 (a necessary growth condition).

If $f(k,r)$ exists, then there must exist a $k$-chromatic graph of girth at least $r$ and minimum degree at least $k-1$ (take $H$ from Lemma 108.1 inside such a high-$\chi$ graph). Lemma 108.2 then forces any such witness graph to have at least \[ 1+(k-1)\sum_{i=0}^{\lfloor (r-3)/2\rfloor}(k-2)^i \] vertices.

5) VERIFICATION (FAST REALITY CHECK)

• If $k=2$, the property is trivial: any graph has a bipartite subgraph with girth $\ge r$ (take a forest). So $f(2,r)=2$ is consistent.
• Lemma 108.1 is the standard "critical subgraph" argument; the coloring extension step uses only the degree bound and pigeonhole.
• Lemma 108.2 BFS-tree counting: the only delicate point is "no cross edges inside the BFS ball"; any such edge would create a cycle of length at most $2t+1<r$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. From any $\chi(G)\ge k$ one can extract a $k$-critical subgraph with $\delta\ge k-1$ (Lemma 108.1), and any graph with $\delta\ge d$ and girth $\ge r$ must be large (Lemma 108.2).

(ii) Exact first gap. A method to pass from high chromatic number to simultaneously (a) girth $\ge r$ and (b) chromatic number $\ge k$ in a subgraph, for all $r\ge4$.

(iii) Top 3 next moves (concrete targets).

1. Develop an iterative deletion process that removes all short cycles while controlling chromatic number, perhaps via degree constraints from Lemma 108.1.
2. Try to prove a "high girth subgraph lemma" using random sparsification plus the Lovász Local Lemma, with a chromatic-number lower bound via minimum degree.
3. Search for candidate counterexample families: graphs with huge chromatic number but forced small cycles everywhere (highly locally dense constructions).

(iv) Minimal counterexample structure. A counterexample for some $(k,r)$ would be a family $G_t$ with $\chi(G_t)\to\infty$ such that every subgraph of girth $\ge r$ has $\chi<k$.