A question of Galvin [Ga73], who proved that this is true with $\mathfrak{m}=\aleph_0$. Galvin also proved that the stronger version of this statement, in which the subgraph is induced, implies $2^{\mathfrak{k}}<2^{\mathfrak{n}}$ for all cardinals $\mathfrak{k}<\mathfrak{n}$.

Komjáth [Ko88b] proved it is consistent that\[2^{\aleph_0}=2^{\aleph_1}=2^{\aleph_2}=\aleph_3\]and that there exist graphs which fail this property (with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$).

Shelah [Sh90] proved that, assuming the axiom of constructibility, the answer is yes with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$.

It remains open whether the answer to this question is yes assuming the Generalized Continuum Hypothesis, for example.

View the LaTeX source

This page was last edited 01 October 2025.