However, some assumption such as the one of being a strongly compact cardinal is necessary: if the generalized continuum hypothesis is true, then for every infinite cardinal , there exists a graph of cardinality such that the chromatic number of is greater than , but such that every subgraph of whose vertex set has smaller power than has chromatic number at most . characterizes the infinite graphs that obey a generalization of the De Bruijn–Erdős theorem, in that their chromatic number is equal to the maximum chromatic number of their strictly smaller subgraphs. Notes References . . . . . . . . . . . . . . . . . . . . . . . . See especially Chapter II.5 "De Bruin–Erdős reduction to finite sets and results near the lower bound", pp. 39–42, and Chapter V.26 "De Bruin–Erdős's theorem and its history", pp. 236–241. Graph coloring Infinite graphs Theorems in graph theory Axiom of choice Paul Erdős