Common finite-chromatic subgraph of two graphs of chromatic number $\aleph_1$ (Erdős #62)
Statement
If $G_1$ and $G_2$ are two graphs each of chromatic number $\aleph_1$ (the first uncountable cardinal), must there exist a graph $G$ of chromatic number $4$ — or even of chromatic number $\aleph_0$ — that is isomorphic to a subgraph of both $G_1$ and $G_2$? Here the chromatic number of an infinite graph is the least cardinal $\kappa$ for which the vertices can be properly coloured with $\kappa$ colours.
Acceptance. FULLY RESOLVES: a proof settling the question — either a proof that any two (equivalently, any finite family of) graphs of chromatic number $\aleph_1$ share a common subgraph of chromatic number $4$ (and/or $\aleph_0$), or a counterexample consisting of two graphs of chromatic number $\aleph_1$ whose common subgraphs all have chromatic number $\leq 3$, together with a proof (relative to a specified model of set theory, clearly flagged, if the answer turns out to be independent of ZFC). A machine-checkable proof is preferred, otherwise a full written proof. ADVANCES: (a) prove the $\aleph_0$ version while leaving the chromatic-number-$4$ version open, or vice versa; (b) prove Erdős's stronger conjecture that every $\aleph_1$-chromatic graph contains all $4$-chromatic graphs of sufficiently large girth (which implies the affirmative answer); (c) establish a consistency or independence result for either version. Deliver the proof file.
Background
Asked by Erdős [Er87], [Er90], [Er95d], a problem in the theory of uncountably chromatic graphs. Erdős also posed the finite-family version: must any finite collection of graphs of chromatic number $\aleph_1$ share a common subgraph of chromatic number $4$ (or $\aleph_0$)? A relevant known result: every graph of chromatic number $\aleph_1$ contains all sufficiently large odd cycles (each of chromatic number $3$), proved by Erdős, Hajnal, and Shelah [EHS74] (see site problem #594). Erdős conjectured that 'probably' every graph of chromatic number $\aleph_1$ contains, as subgraphs, all graphs of chromatic number $4$ with sufficiently large girth — which would answer the present question affirmatively at chromatic number $4$. No cash prize is attached. Listed as open on erdosproblems.com/62 (fetched 2026-07-13, status 'open', tagged 'graph theory'). The attacker's tool: infinite and set-theoretic combinatorics — partition calculus, elementary-submodel arguments, and forcing/absoluteness techniques applied to the structure theory of uncountably chromatic graphs; there is essentially no finite computational purchase.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #62 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.