NOT PROVABLE
Open in general, but there exist models of set theory where the result is false.
Let $G$ be a graph with chromatic number $\aleph_1$. Is there, for every cardinal number $m$, some graph $G_m$ of chromatic number $m$ such that every finite subgraph of $G_m$ is a subgraph of $G$?
A conjecture of Walter Taylor. The more general problem replaces $\aleph_1$ with any uncountable cardinal $\kappa$.
More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.
Komjáth
[KoSh05] proved that it is consistent that the answer is no, in that there exists a graph $G$ with chromatic number $\aleph_1$ such that if $H$ is any graph all of whose finite subgraphs are subgraphs of $G$ then $H$ has chromatic number $\leq \aleph_2$.
View the LaTeX source
This page was last edited 01 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #736, https://www.erdosproblems.com/736, accessed 2026-01-14
