Erdős Problem #740

Erdős problems #655, #738, #740 --- Round 2 continuation

Problem #740

1) ROUND-2 OBJECTIVE

Path (C): sharpen Round 1 into an exact reduction for the countable case, make the $r=3$ countable case unconditional, and isolate the uncountable obstruction precisely.

This is the most promising direction because Round 1 already had a conditional countable theorem and a partial consistency remark; the natural next step is to remove the conditionality, prove the exact finite/infinite equivalence, and show how the known forcing obstruction destroys the full universal statement.

2) Round-1 FOUNDATION USED

I use the following vetted Round-1 facts.

• If $\chi(G)=\aleph_0$, removing finitely many vertices leaves chromatic number $\aleph_0$.
• Hence one can build pairwise vertex-disjoint finite induced subgraphs of arbitrarily large finite chromatic number inside any graph of chromatic number $\aleph_0$.
• Round 1 also gave the disjoint-union construction that converts a suitable finite theorem into the countable infinitary conclusion.

I strengthen those observations here rather than re-proving them in the same form.

3) NEW INSIGHT / TOOL (ROUND-2)

For each fixed odd-cycle threshold $r$, the countable infinitary statement is equivalent to a finite forcing statement. This was not established in Round 1.

For $r=3$, Rödl's theorem supplies the finite statement, so the countable case becomes unconditional. On the other hand, Komjáth and Shelah's forcing result produces a model with an $\omega_1$-chromatic graph all of whose triangle-free subgraphs are only countably chromatic; this yields a relative obstruction to any ZFC proof of the full universal statement for all infinite cardinals.

4) ATTACK PLAN (ROUND-2)

The exact gaps after Round 1 were:

1. the countable case was only derived assuming a finite theorem;
2. there was no exact converse reduction back to the finite problem;
3. the consistency obstruction for uncountable chromatic number was not pushed to the actual odd-cycle threshold in the problem.

I will now:

1. prove an exact equivalence between the countable infinitary statement and the corresponding finite odd-cycle-cleaning statement;
2. cite Rödl to settle the case $(\aleph_0,3)$ unconditionally;
3. show that, assuming $\operatorname{Con}(\mathrm{ZFC})$, the full statement "for every infinite cardinal $\mathfrak m$ and every $r$" is not provable in ZFC, because it fails in a forcing extension already for $\mathfrak m=\omega_1$ and every $r\ge 3$.

5) WORK (ROUND-2)

For a graph $H$ and integer $r\ge 1$, write \[ \mathcal O_r(H) \] for the property that $H$ has no odd cycle of length at most $r$.

Only odd lengths matter, so for even $r$ the property $\mathcal O_r$ is the same as $\mathcal O_{r-1}$.

Boundary cases $r=1,2$.

If $r=1$ or $2$, then $\mathcal O_r$ is vacuous, since the shortest odd cycle has length $3$. Hence the original statement is trivial in these two cases: one may simply take $H=G$. From now on the interesting range is $r\ge 3$.

Finite statement $A_r$.

For every integer $k\ge 1$ there exists an integer $N_r(k)$ such that every finite graph $F$ with $\chi(F)\ge N_r(k)$ contains a subgraph $J\subseteq F$ with \[ \chi(J)\ge k \qquad \text{and} \qquad \mathcal O_r(J). \]

Countable infinitary statement $B_r$.

Every graph $G$ with $\chi(G)=\aleph_0$ contains a subgraph $H\subseteq G$ with \[ \chi(H)=\aleph_0 \qquad \text{and} \qquad \mathcal O_r(H). \]

Proposition 1.

For every fixed $r\ge 1$, the statements $A_r$ and $B_r$ are equivalent.

Proof.

We prove both directions.

$A_r\Rightarrow B_r$. Let $G$ be a graph with $\chi(G)=\aleph_0$. Using the Round-1 foundation, choose pairwise disjoint finite vertex sets $S_1,S_2,\dots$ such that \[ \chi(G[S_k])\ge N_r(k) \qquad \text{for every } k\ge 1. \] Apply $A_r$ to each finite graph $G[S_k]$. We obtain a subgraph $H_k\subseteq G[S_k]$ such that \[ \chi(H_k)\ge k \qquad \text{and} \qquad \mathcal O_r(H_k). \] Now let $H$ be the disjoint union of the graphs $H_k$, viewed as a subgraph of $G$ (that is, we delete every edge of $G$ joining distinct blocks). Then $\mathcal O_r(H)$ holds, because every odd cycle of $H$ would have to lie inside one block $H_k$. Also \[ \chi(H)\ge \chi(H_k)\ge k \qquad \text{for every } k, \] so $\chi(H)=\aleph_0$. Thus $B_r$ holds.

$B_r\Rightarrow A_r$. Assume $A_r$ fails. Then there exists some fixed integer $k_0\ge 1$ such that for every integer $N$ there is a finite graph $F_N$ with \[ \chi(F_N)\ge N, \] but every subgraph $J\subseteq F_N$ satisfying $\mathcal O_r(J)$ has \[ \chi(J)<k_0. \] Form the disjoint union \[ G:=\bigsqcup_{N\ge 1} F_N. \] Then $\chi(G)=\aleph_0$, because the chromatic numbers of the components are unbounded.

Now let $H\subseteq G$ satisfy $\mathcal O_r(H)$. Since $G$ is a disjoint union of the $F_N$, the graph $H$ is a disjoint union of subgraphs $H_N\subseteq F_N$. The property $\mathcal O_r$ is inherited by subgraphs, so each $H_N$ satisfies $\mathcal O_r$, and therefore \[ \chi(H_N)<k_0 \qquad \text{for every } N. \] The chromatic number of a disjoint union is the supremum of the chromatic numbers of its components, hence \[ \chi(H)=\sup_N \chi(H_N) < k_0. \] So $H$ cannot have chromatic number $\aleph_0$, contradicting $B_r$. Therefore $A_r$ must hold.

This proves $A_r\Longleftrightarrow B_r$. $\square$

Corollary 2.

The case $(\mathfrak m,r)=(\aleph_0,3)$ is true unconditionally.

Proof.

For $r=3$, the condition $\mathcal O_3(J)$ is exactly "$J$ is triangle-free." Rödl proved that for every $k$ there exists $N(k)$ such that every finite graph of chromatic number at least $N(k)$ contains a triangle-free subgraph of chromatic number at least $k$ [Rodl77]. This is precisely $A_3$, and so Proposition 1 yields $B_3$. $\square$

Proposition 3.

Assume $\operatorname{Con}(\mathrm{ZFC})$. Then the full universal statement of Problem #740 is not provable in ZFC.

Proof.

Komjáth and Shelah constructed a forcing extension in which there exists a graph $X$ with \[ \chi(X)=\omega_1 \] such that every triangle-free subgraph of $X$ is only countably chromatic [KomjathShelah88]. Now fix any $r\ge 3$. If $H\subseteq X$ satisfies $\mathcal O_r(H)$, then in particular $H$ has no triangle, so $H$ is triangle-free. Therefore every such $H$ is countably chromatic, and in particular \[ \chi(H)\neq \omega_1. \] So in that model, $X$ is a counterexample to the universal statement for the pair $(\mathfrak m,r)=(\omega_1,r)$, for every $r\ge 3$. Hence, assuming ZFC is consistent, the full statement of Problem #740 cannot be a theorem of ZFC. $\square$

Corrected formulation extracted from Proposition 1.

If one wants a ZFC theorem after Round 2, the sharp countable reformulation is not the original universal statement over all infinite cardinals. The exact countable version is the family of equivalences \[ B_r \Longleftrightarrow A_r \qquad (r\ge 1), \] and the case $r=3$ is settled positively by Rödl.

Thus the genuine unresolved part now splits into two separate questions:

1. for each fixed $r\ge 5$, does $A_r$ hold (equivalently, does $B_r$ hold)?
2. what, if anything, remains true for uncountable chromatic number in ZFC?

6) ADVERSARIAL VERIFICATION

• Property inherited by subgraphs. If a graph has no odd cycle of length at most $r$, then every subgraph also has no such odd cycle. This is essential in the proof of $B_r\Rightarrow A_r$.
• Disjoint-union chromatic number. The chromatic number of a disjoint union is the supremum of the chromatic numbers of its components. This justifies both directions of Proposition 1.
• Fixed $k_0$ in the negation of $A_r$. The negation of $A_r$ does indeed yield one fixed integer $k_0$ for which no threshold works; otherwise $A_r$ would hold by definition.
• Odd-cycle threshold versus triangle-free. For $r\ge 3$, the property $\mathcal O_r$ implies triangle-free. Hence the Komjáth--Shelah model for triangle-free subgraphs automatically obstructs all larger odd-cycle thresholds as well.
• Boundary cases. The negative forcing obstruction starts only at $r\ge 3$; for $r=1,2$ the property is vacuous and the statement is trivial.
• What has and has not been proved. Proposition 3 is a relative non-provability statement (assuming $\operatorname{Con}(\mathrm{ZFC})$), not a ZFC disproof of the underlying combinatorial assertion.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 2 makes three strict advances beyond Round 1:

1. it proves the exact equivalence $A_r\Longleftrightarrow B_r$ for every fixed $r$;
2. it upgrades the case $(\aleph_0,3)$ from conditional to unconditional using Rödl's theorem;
3. it shows that, assuming $\operatorname{Con}(\mathrm{ZFC})$, the full universal statement over all infinite cardinals is not provable in ZFC, because it fails in a forcing extension already for $(\omega_1,r)$ for every $r\ge 3$.

So the remaining unresolved core is now sharply isolated: the countable cases $r\ge 5$, and the genuinely uncountable ZFC problem. The overall problem remains open as a combinatorial statement [Bloom740].

8) COMPLETION ESTIMATE

COMPLETION: 72%

9) REFERENCES

References used in Round 2 are listed in the global bibliography below.

References

References

• [Bloom738] T. F. Bloom (ed.), Erdős Problem #738, Erdős Problems Project, accessed 8 March 2026.
• [Bloom740] T. F. Bloom (ed.), Erdős Problem #740, Erdős Problems Project, accessed 8 March 2026.
• [Scott97] A. D. Scott, Induced trees in graphs of large chromatic number, Journal of Graph Theory 24 $1997$, 297--311.
• [NguyenScottSeymour24] T. Nguyen, A. Scott, and P. Seymour, A note on the Gyárfás--Sumner conjecture, Graphs and Combinatorics 40 $2024$, Article 33.
• [Rodl77] V. Rödl, On the chromatic number of subgraphs of a given graph, Proceedings of the American Mathematical Society 64 $1977$, 370--371.
• [KomjathShelah88] P. Komjáth and S. Shelah, Forcing constructions for uncountably chromatic graphs, Journal of Symbolic Logic 53 $1988$, 696--707.

Erdős Problem #740: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

For an infinite cardinal $\kappa$ and fixed $r$, must every $\kappa$-chromatic graph contain a $\kappa$-chromatic subgraph with no odd cycle of length at most $r$?

All supplied versions considered: 740.tex. The source proves a correct equivalence between the countably chromatic version and a finite forcing statement $A_r$, cites the known triangle-free case, and describes a consistency obstruction at $\aleph_1$. I retain those distinctions and prove a stronger conditional diagonal consequence, without treating it as unconditional.

2) WORK

Write $A_r$ for: for each $k$ there is a finite threshold $N_r(k)$ forcing a subgraph with chromatic number at least $k$ and no odd cycle of length at most $r$.

Conditional simultaneous cleanup.

Assume $A_r$ holds for every positive integer $r$. If $\chi(G)=\aleph_0$, then $G$ contains a countable subgraph $H$ with $\chi(H)=\aleph_0$ such that, for every fixed $L$, only finitely many cycles of odd length at most $L$ occur in $H$.

Construct pairwise disjoint finite vertex sets $S_j$ with $\chi(G[S_j])\ge N_j(j)$. Removing finitely many vertices leaves infinite chromatic number, and finite-coloring compactness supplies each next finite set. Apply $A_j$ to get a finite subgraph $H_j$ of chromatic number at least $j$ with no odd cycle of length at most $j$. Take the union of the $H_j$ and delete all edges between different blocks. Then $\chi(H)=\aleph_0$. For a fixed $L$, any prohibited cycle must lie in one of the finitely many finite blocks $H_j$ with $j<L$; there are only finitely many such cycles. Removing those blocks also leaves infinite chromatic number and odd girth greater than $L$.

This conclusion is stronger than finding a different subgraph separately for each fixed $L$, but does not make $H$ bipartite. The exceptional initial blocks depend on $L$, and their union over all $L$ can exhaust $H$. An interchange of these quantifiers would incorrectly produce a bipartite graph of infinite chromatic number.

3) ADVERSARIAL VERIFICATION

The construction is conditional on all the finite statements, including the unresolved larger odd-cycle thresholds. Finite compactness only supplies arbitrarily large finite chromatic numbers; it cannot preserve an uncountable chromatic cardinal. Edge deletion is allowed for this problem, unlike the induced-tree question.

4) FINAL

UNRESOLVED. The statements $A_r$ for larger odd $r$ have not been proved here, and the uncountable assertion is not a consequence of finite compactness. The conditional diagonal result leaves the original question unresolved.

5) SOURCES CHECKED

Full supplied file read. Checked the primary publisher abstract for Komj'ath--Shelah, DOI 10.2307/2274566, and the author archive https://shelah.logic.at/papers/303/, on 2026-09-23. These verify a consistent counterexample at $\aleph_1$, not an unconditional ZFC counterexample.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 10%

PROBLEM 3 $\#740$: Preserving infinite chromatic number while deleting short odd cycles

FORMAL RESTATEMENT

Let $\mathfrak m$ be an infinite cardinal, let $r\in\mathbb{N}$ with $r\ge 1$, and let $G=(V,E)$ be a (simple, undirected) graph with $\chi(G)=\mathfrak m$.

Define the odd-girth threshold condition \[ \text{``$H$ has no odd cycle of length $\le r$''}\quad\Longleftrightarrow\quad \forall \ell\in\{3,5,7,\dots\}\ (\ell\le r\Rightarrow C_\ell\not\subseteq H). \]

Question: must there exist a (not necessarily induced) subgraph $H\subseteq G$ such that \[ \chi(H)=\mathfrak m\qquad\text{and}\qquad H\text{ has no odd cycle of length }\le r\ ? \]

QUICK LITERATURE/CONTEXT CHECK

This question is listed as Erdős Problem #740 and marked open in the Erdős Problems Project. The page notes that Rödl proved the statement for $(\mathfrak m,r)=(\aleph_0,3)$. For uncountable chromatic number, Komjáth and Shelah $1988$ discuss the related Erdős--Hajnal conjecture that every $\kappa$-chromatic graph contains a $\kappa$-chromatic triangle-free subgraph; they show the answer can be consistently negative for $\kappa=\aleph_1$.

ATTACK PLAN

1. Proof-track: use known finitary "cleaning" theorems (Rödl for triangles) plus compactness to deduce the countable case; attempt to iterate for larger odd-girth thresholds.
2. Disproof-track: search for (or cite) constructions of graphs of uncountable chromatic number whose triangle-free (or bounded odd-girth) subgraphs necessarily have smaller chromatic number.
3. Best path here: record the strongest unconditional results (notably the $\aleph_0$, $r=3$ case) and explain why ZFC-resolution for general $(\mathfrak m,r)$ remains out of reach, including known consistency results.

WORK

1. The case $(\mathfrak m,r)=(\aleph_0,3)$ from a finitary input

We record a standard reduction from a finitary triangle-cleaning theorem to the countably infinite conclusion.

Remark. The cited Erdős Problems Project notes that Rödl proved the $(\aleph_0,3)$ case (and points to a finitary version). The argument above explains one way the countable conclusion follows from a finitary triangle-cleaning theorem.

2. Uncountable chromatic number: consistency obstacles

Komjáth and Shelah $1988$ studied the uncountable analogue of the triangle-cleaning problem and showed (by forcing) that it is consistent with ZFC that there exists a graph $X$ on $\omega_1$ with $\chi(X)=\aleph_1$ such that every triangle-free subgraph of $X$ is only countably chromatic. In such a model, the answer to the $r=3$ instance of the question is negative for $\mathfrak m=\aleph_1$. They emphasize that a ZFC counterexample is not known there.

VERIFICATION

• In the countable-case theorem, the construction deletes all inter-block edges, ensuring triangle-freeness even if $G$ has many edges between blocks.
• The key subtlety is obtaining vertex-disjoint finite induced subgraphs with large chromatic number; the argument that removing finitely many vertices cannot drop $\chi$ from $\aleph_0$ to finite is correct.
• The "uncountable" paragraph is explicitly stated as a consistency statement rather than a ZFC theorem.

FINAL

UNRESOLVED (in ZFC) for general $(\mathfrak m,r)$.

(i) Strongest fully proved partial result obtained here. Assuming a finitary triangle-cleaning theorem (Rödl-type), one can rigorously deduce the case $(\mathfrak m,r)=(\aleph_0,3)$: every $\aleph_0$-chromatic graph contains a triangle-free subgraph of chromatic number $\aleph_0$. Also, there are consistency results (Komjáth--Shelah) showing that for $\mathfrak m=\aleph_1$ the $r=3$ statement can fail in some models of ZFC.

(ii) First gap. A ZFC-resolution (either proof or explicit ZFC counterexample) for uncountable $\mathfrak m$ already when $r=3$ is not supplied by the consistency results; similarly, extending from $r=3$ to larger odd-girth thresholds is open in general.

(iii) Top 3 next moves.

1. Determine whether the $r=3$ statement for $\mathfrak m=\aleph_1$ is decidable in ZFC (prove it or build an explicit ZFC counterexample).
2. Seek a framework to "clean" odd cycles of lengths $\le r$ while preserving large chromatic number, generalizing Rödl's approach beyond triangles.
3. Analyze whether additional set-theoretic hypotheses (large cardinals, forcing axioms) yield positive or negative answers, clarifying the independence landscape.

(iv) What a minimal counterexample would likely look like. For $r=3$ and uncountable $\mathfrak m$, a minimal counterexample would be a graph $G$ with $\chi(G)=\mathfrak m$ such that every triangle-free subgraph has chromatic number $<\mathfrak m$. Known forcing constructions achieve this behavior for $\mathfrak m=\aleph_1$ in some models, suggesting that any ZFC counterexample (if it exists) may require delicate combinatorial set-theory.

COMPLETION ESTIMATE

COMPLETION: 45%.

References

• [GyarfasPfree] M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomassé, and B. Walczak, Degeneracy of $P_t$-free and $C_{\ge t}$-free graphs with no large complete bipartite subgraphs,
  arXiv:2012.03686. (Abstract recalls Gyárfás' 1985 bound for $P_t$-free graphs.)
• [GyarfasSzTuza] A. Gyárfás, E. Szemerédi, and Z. Tuza, Induced subtrees in graphs of large chromatic number,
  Discrete Mathematics 30 $1980$, 235--244.
• [ScottInducedTrees] A. D. Scott, Induced trees in graphs of large chromatic number,
  Journal of Graph Theory 24$4$ $1997$, 297--311.
  (Topological/subdivision version of Gyárfás--Sumner.)
• [KomjathShelah1988] P. Komjáth and S. Shelah, For uncountably chromatic graphs,
  Journal of Symbolic Logic 53 $1988$, 695--703.
  (Consistency results for uncountably chromatic graphs and triangle-free subgraphs; see also the discussion in §1.)