Erdős #595 — K4-free graph not a countable union of triangle-free graphs

Statement

Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many ($\aleph_0$) triangle-free graphs? Equivalently: must every edge set of a $K_4$-free graph be coverable by countably many triangle-free subgraphs, or does there exist a $K_4$-free $G$ that resists any such countable covering?

Facts

- Prize \$250; status OPEN per erdosproblems.com/595 (site-owner belief) — "this is open, and cannot be resolved with a finite computation." - Falsifiable: no — an infinite object is asserted to exist (or not); no finite counterexample or finite search settles either direction. - Origin: a problem of Erdős and Hajnal, cited on erdosproblems.com as [Er87] = P. Erdős, "Some problems on finite and infinite graphs," Logic and Combinatorics (Arcata, Calif., 1985), 1987, 223-228 (MR 891250) — restating the older Erdős–Hajnal, "On decomposition of graphs," Acta Math. Acad. Sci. Hungar. 18 (1967), 359-377 (https://link.springer.com/article/10.1007/BF02280296). - Known results / best bounds: Folkman, "Graphs with monochromatic complete subgraphs in every edge coloring," SIAM J. Appl. Math. 18 (1970), 19-24 [Fo70], and Nešetřil–Rödl, "Type theory of partition properties of graphs" (1975) [NeRo75] (also stated as Nešetřil– Rödl, J. Comb. Theory (B) 20 (1976), 243-249 on the UCSD mirror), proved the finite analogue: for every $n\ge 1$ there is a $K_4$-free graph that is not the union of $n$ triangle-free graphs. This is exactly the existence half of the classical Folkman-number theory quantified in erdos/582 (PROVED, Lean-verified — current best bound $21\le f(2,3,4)\le 786$, erdosproblems.com/582). Passing from "for every finite $n$" to "even for $\aleph_0$" is precisely what #595 asks, and it is not a routine compactness step because triangle-free graphs can themselves have unbounded (even uncountable) chromatic number, so no easy product-coloring argument bounds the countable union. On the countably-infinite question itself: Shelah proved consistency of a "yes" witness. S. Shelah, "Consistency of positive partition theorems for graphs and models," in Set Theory and its Applications (Toronto, ON, 1987), Lecture Notes in Math. 1401, Springer (1989), 167-193, shows (via forcing) that it is consistent with ZFC that such a $K_4$-free, non-countably-triangle-free-coverable graph $G$ exists — but it is *not known* whether this is provable in ZFC outright (source: https://mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/InfiniteTriangleFreeCovering.html, an independently curated older UCSD "Erdős Problems" mirror that states this explicitly and is the *only* source found that credits Shelah on this exact problem). The current erdosproblems.com/595 page does not cite Shelah or mention this consistency result at all — it lists only [Fo70]/[NeRo75] and "See also [582] and [596]." - Related problems: erdos/582 erdos/596

Literature state

- erdosproblems.com/595 (accessed 2026-07-02): status OPEN, 0 comments, no partial solutions recorded in the site's forum; "Formalised statement?" = Yes (the statement, not a proof, has been formalized — presumably in the google-deepmind/formal-conjectures Lean repo referenced by the teorth database). - The UCSD mirror (mathweb.ucsd.edu/~erdosproblems), curated independently of Bloom's erdosproblems.com, frames the identical problem as "Infinite $K_4$-free graphs are the union of triangle-free countable graphs" (\$250, attributed to Hajnal) and states: "Shelah [2] proved that the existence of such a graph is consistent but it is not known if this is provable in ZFC" — a genuine partial result missing from the current erdosproblems.com page. This is the single most important literature-search finding here: #595 is not merely "no progress," it already has a one-directional consistency result from 1987/89 that the primary tracking site omits. - github.com/teorth/erdosproblems community database (data/problems.yaml, accessed 2026-07-02) still records #595 status.state: open and does *not* place it in the site-wide "not provable" / "not disprovable" / "independent" buckets (3 + 4 + 3 problems total across the whole 1217-problem database as of this access). This is consistent with only ONE direction of consistency being established (Shelah: "yes-witness" consistent); a full ZFC-independence classification would additionally require a model of ZFC in which *every* $K_4$-free graph IS a countable union of triangle-free graphs — no such result was found in any source searched. - Sibling forcing construction in the same $K_4$/triangle family: Komjáth and Shelah, "Forcing constructions for uncountably chromatic graphs," J. Symbolic Logic 53 (1988), 696-707, build (consistently, by forcing) a $K_4$-free graph $G$ with chromatic number $\omega_1$ such that every subgraph of $G$ with uncountable chromatic number contains a triangle (cited as Conjecture 2.1 in D. T. Soukup, "Open problems around uncountable graphs" (2015 lecture notes), https://danieltsoukup.github.io/academic/norwich_handout.pdf, §2: "Consistently yes (even $K_4$ can be omitted in $G$, while CH may or may not hold) [Komjáth–Shelah 1988]. ... The problem is still open in ZFC."). This is a *different* statement (chromatic number vs. edge-coverability by countably many triangle-free graphs) but uses the same circle of ccc/proper-forcing techniques on $K_4$-free graphs and is the closest published machinery to what a #595 consistency proof needs. - #596 (erdosproblems.com/596, accessed 2026-07-02) states the general dichotomy of which #595 is one instance, and records that the analogous pair $(G_1,G_2)=(C_4,C_6)$ is resolved: Nešetřil–Rödl proved the finite-Folkman-type property for that pair, and Erdős–Hajnal proved "every $C_4$-free graph is a countable union of trees" — giving a full "yes, countable covering always succeeds" answer there. #595 is literally the open, harder $K_4/K_3$ instance of the same question. - No arXiv preprint, Lean formalization of a *proof* (only of the *statement*), or AI-assisted progress specific to #595 was found (searched arXiv, WebSearch-mediated Google Scholar, OpenAlex, and the teorth/erdosproblems "AI contributions" wiki index, which lists no entry for #595 as of 2026-06-30 per its own changelog). Recent (2025-2026) Folkman-graph papers found — arXiv:2506.14942 "Some remarks on Folkman graphs for triangles" (Hermitian-unital geometric constructions for $f(2,3,4)$), arXiv:2203.15764 "10 Problems for Partitions of Triangle-free Graphs" — address only the finite Folkman-number side (i.e. feed erdos/582, not #595).

Attack surface

- Mode: derivation+formalization (this is a set-theory/forcing problem; falsifiability is "not-finite" per the site, so no computational search applies). - Concrete first experiment: not a search — a literature-derivation task. (1) Obtain Shelah's 1989 LNM 1401 pp. 167-193 in full and extract the actual forcing poset used to build the "yes"-witness $G$; check whether the generic object is canonical/definable enough that the construction could plausibly be de-forced into a ZFC theorem (the historical pattern by which some Shelah-era forcing constructions were later replaced by explicit ZFC constructions, e.g. via Todorcevic's walks-on-ordinals methods). (2) Cross-check whether the Komjáth–Shelah 1988 (JSL) generic graph for the sibling chromatic-number problem already happens to witness #595's covering-failure property (it is $K_4$-free and forcing-built in the same family) — if so this would at minimum tighten/duplicate Shelah's citation and could be written up to fix the gap on erdosproblems.com/595 itself. - Oracle: a ZFC "yes" proof is verified by exhibiting $G$ ($K_4$-free) and showing, for every countable family $\{H_i\}_{i<\omega}$ of triangle-free graphs with $\bigcup_i H_i = G$ (as edge sets), that some $H_i$ contains a triangle (contradiction). A ZFC "no" proof is verified by an explicit countable-coloring algorithm valid for every $K_4$-free $G$. A forcing-consistency claim is verified by checking the poset is ccc/ proper and the generic object has the stated property — not mechanically checkable by us, but in principle formalizable (the problem's *statement* is already marked "Formalised: Yes" on erdosproblems.com). - Feasibility: famous-and-hard for a fresh ZFC resolution — it sits inside the Erdős–Hajnal infinite partition-calculus program (1967-present, Komjáth/Shelah/Soukup/ Todorcevic) which has not closed the ZFC gap for the $K_4$/$K_3$ case in ~60 years, in contrast to the fully-resolved $C_4/C_6$ case (#596). Realistically in reach for us only as a literature-completion task: read-and-verify Shelah 1989 + Komjáth–Shelah 1988, confirm/refute whether the latter's construction transfers, and (if so) submit the citation fix to erdosproblems.com — not a fresh proof attempt.

Related

- erdos/582 — the finite Folkman-number ancestor: existence of a $K_4$-free graph forcing a monochromatic triangle under any *finite* edge-coloring (Folkman 1970, Nešetřil–Rödl 1975/76); PROVED and Lean-verified, with quantitative bounds $21\le f(2,3,4)\le786$. #595 asks whether the same phenomenon survives passing from finite to $\aleph_0$ colors. - erdos/596 — the general $(G_1,G_2)$ dichotomy of which #595 is the open $K_4/K_3$ instance; the $C_4/C_6$ instance is fully resolved (every $C_4$-free graph is a countable union of trees, Erdős–Hajnal + Nešetřil–Rödl). - concept/forcing — Shelah's technique (ccc/proper forcing over a poset of finite approximations) is the *only* known route to a partial result here (consistency of a "yes"-witness), and is also the technique behind the sibling Komjáth–Shelah 1988 construction. - concept/folkman-numbers — the finite quantitative theory ($f(2,3,4)$ etc.) that this problem generalizes to countably-infinite colorings. - concept/partition-calculus — the Erdős–Hajnal–Rado infinite Ramsey/partition-relation framework (arrow notation, e.g. $\alpha\to(\alpha,3)^2$) that #595 lives inside; see also Soukup's "Open problems around uncountable graphs" survey for the wider family of open instances. - concept/uncountable-chromatic-graphs — the parallel program (Komjáth, Shelah, Soukup) building $K_4$-free graphs with uncountable chromatic number where every uncountable-chromatic subgraph contains a triangle; closest published forcing machinery to what #595 needs. - concept/zfc-independence — the real open question for #595 is whether it is provable in ZFC, refutable in ZFC, or genuinely independent; only the "consistent yes" direction (Shelah) is currently established, so full independence has *not* been shown.