Reused writeup on Math-865 (gpt pro 5.2)

Erdős Problem 595 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal. Folkman [Fo70] and Nešetřil and Rödl [NeRo75] have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs. See also [582] and [596] . References [Fo70] Folkman, Jon, Graphs with monochromatic complete subgraphs in every edge coloring . SIAM J. Appl. Math. $1970$, 19-24. [NeRo75] Nes̆etr̆il, Jaroslav and Rödl, Vojtěch, Type theory of partition properties of graphs . $1975$, 405-412.

FORMAL RESTATEMENT

A (simple, undirected) graph is $G=(V,E)$ with $E\subseteq [V]^2$. A graph is $K_4$-free if it has no 4-vertex clique. A graph is triangle-free if it has no 3-vertex clique.

Say that $G$ is a countable union of triangle-free graphs if there exist edge-sets $E_0,E_1,\dots\subseteq E$ such that $E=\bigcup_{n<\omega} E_n$ and each graph $(V,E_n)$ is triangle-free.

Question: Does there exist an infinite (necessarily uncountable, see Lemma lem:countable_trivial) $K_4$-free graph $G$ such that $E(G)$ is not a countable union of triangle-free graphs? Equivalently: does there exist an infinite $K_4$-free graph $G$ such that every countable edge-colouring of $E(G)$ yields a monochromatic triangle?

QUICK LITERATURE/CONTEXT CHECK

I will not import external results beyond what is explicitly stated in the problem text. The text states that for each finite $n$ there is a (necessarily finite or infinite) $K_4$-free graph not decomposable into $n$ triangle-free graphs (Folkman; Nešetřil--Rödl). The question asks for the countably infinite version ($n=\aleph_0$), and is presented as open.

ATTACK PLAN

Proof-track (existence) ideas.

• Try to build an uncountable $K_4$-free graph $G$ with strong edge-Ramsey property $G\to(K_3)_{\aleph_0}$ (every countable edge-colouring yields monochromatic triangle), e.g. via transfinite recursion ensuring that each new vertex "codes" many constraints.
• Use known finite $n$-Folkman graphs as building blocks and attempt a compactness/limit argument to force monochromatic triangles for countably many colours.

Disproof-track (nonexistence) ideas.

• Attempt to prove that every $K_4$-free graph admits a countable edge-colouring with no monochromatic triangle, perhaps by decomposing edges into countably many triangle-free subgraphs using structural properties of $K_4$-free graphs.
• Try to show any $K_4$-free graph has "countable triangle arboricity" (a countable decomposition avoiding monochromatic triangles) by a rank decomposition of triangles.

I did not resolve existence/nonexistence. I record two equivalences/necessary conditions that constrain any counterexample.

WORK

FAST REALITY CHECK

• For $n=1$: a graph is not the union of $1$ triangle-free graph exactly if it contains a triangle. There are infinite $K_4$-free graphs with triangles (e.g. a disjoint union of infinitely many triangles), so the finite-$n$ analogue is trivial for $n=1$.
• For countably many colours, if $G$ is countable then one can colour edges injectively with $\omega$ colours, so there is no monochromatic triangle. Thus any counterexample must be uncountable (Lemma lem:countable_trivial).

Lemma 1 (countable union vs countable edge-colouring). For a graph $G=(V,E)$, the following are equivalent:

1. $E$ is a countable union of triangle-free edge-sets, i.e. $E=\bigcup_{n<\omega} E_n$ with each $(V,E_n)$ triangle-free.
2. There exists a colouring $\kappa:E\to\omega$ such that for each $n<\omega$, the colour class $E_n:=\kappa^{-1}(\{n\})$ is triangle-free. Equivalently, $\kappa$ has no monochromatic triangle.

Proof. $1$$\Rightarrow$$2$: Given $E=\bigcup_{n<\omega} E_n$ with each $(V,E_n)$ triangle-free, define a colouring $\kappa:E\to\omega$ by \[ \kappa(e):=\min\{n\in\omega: e\in E_n\}. \] Then $\kappa$ is well-defined since the $E_n$ cover $E$. Fix $n$ and consider the colour class $\kappa^{-1}(\{n\})$. By definition, $\kappa^{-1}(\{n\})\subseteq E_n$. Any subgraph of a triangle-free graph is triangle-free, so $(V,\kappa^{-1}(\{n\}))$ is triangle-free. Hence there is no monochromatic triangle.

$2$$\Rightarrow$$1$: Given $\kappa:E\to\omega$, let $E_n:=\kappa^{-1}(\{n\})$. Then $E=\bigcup_{n<\omega}E_n$ and each $(V,E_n)$ is triangle-free because otherwise a triangle in $(V,E_n)$ would be a monochromatic triangle of colour $n$. $\square$

Lemma 2 (countable graphs are never counterexamples). If a graph $G=(V,E)$ has countably many edges (in particular if $V$ is countable), then $G$ is a countable union of triangle-free graphs.

Proof. Enumerate the edges as $E=\{e_0,e_1,e_2,\dots\}$. For each $n$, let $E_n:=\{e_n\}$. Then each $(V,E_n)$ has at most one edge and hence is triangle-free. Moreover $E=\bigcup_{n<\omega} E_n$. So $G$ is a countable union of triangle-free graphs.$\square$

VERIFICATION

• Lemma lem:countable_union_colouring uses the "minimal index" trick to pass from a cover to a genuine colouring; the triangle-free property is preserved under taking subsets.
• Lemma lem:countable_trivial shows that any genuine counterexample must be uncountable (at least uncountably many edges). This matches the intuition that the question is only nontrivial in the uncountable regime.

FINAL

UNRESOLVED

(i) Strongest proved partial result. The problem is equivalent to asking whether there exists a $K_4$-free graph $G$ such that every countable edge-colouring of $E(G)$ has a monochromatic triangle (Lemma lem:countable_union_colouring). Any such $G$ must be uncountable (Lemma lem:countable_trivial).

(ii) First gap (crisp). Either construct an uncountable $K_4$-free graph $G$ with the Ramsey property $G\to(K_3)_{\aleph_0}$, or prove that every $K_4$-free graph admits a countable edge-colouring with no monochromatic triangle.

(iii) Top 3 next moves.

1. Try to prove a decomposition theorem for $K_4$-free graphs: can one cover $E(G)$ by countably many triangle-free subgraphs via a transfinite rank on edges/triangles?
2. Construct candidate counterexamples from known finite $n$-Folkman graphs by transfinite "amalgamation" ensuring $K_4$-freeness is preserved while forcing monochromatic triangles for any countable colouring.
3. Run small-model computations for finite approximations: search for graphs $G$ with $\omega$-like decomposition obstructions to guide an infinite construction.

(iv) Minimal counterexample structure. Any counterexample must be uncountable and $K_4$-free, yet so edge-Ramsey for triangles that countably many colours cannot destroy all monochromatic triangles. Since $K_4$-free graphs can still have many triangles, a counterexample would likely have triangles "spread" so that any countable partition of edges captures an entire triangle in some part.

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.