# “Compactness” theorem for the coloring number

For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdos and De Bruijn stating that if an infinite graph $G$ has finite chromatic number, then there is a finite subgraph $G_0\subseteq G$ such that $\chi(G_0) = \chi(G)$.

For any simple, undirected graph $G=(V,E)$ we set $\text{col}(G) = \sup\{\delta(H): H\subseteq G\}+1$, where $\delta(\cdot)$ denotes the minimal degree. We have $\chi(G) \leq \text{col}(G)$ for any graph $G$. Does the compactness theorem above hold for $\text{col}(\cdot)$, that is, if $\text{col}(G)$ is finite, is there $G_0\subseteq G$ such that $\text{col}(G_0) = \text{col}(G)$?

• It is the minimal degree - sorry, I should have included this in the post, will do. – Dominic van der Zypen Nov 1 '17 at 14:11
• Are $H$ restricted to be finite subgraphs? – Mikhail Tikhomirov Nov 1 '17 at 14:22
• A line infinite in both directions seems to be a counterexample. – Emil Jeřábek Nov 1 '17 at 14:36
• The comment from @EmilJeřábek should probably be an (accepted) answer, so that the stackexchange software doesn't count this question as unanswered. – Andreas Blass Nov 1 '17 at 16:36

A line infinite in both directions has minimal degree $2$, but any its proper subgraph has minimal degree $1$ or $0$. Thus, $\mathrm{col}(G)=3$, but $\mathrm{col}(G_0)\le2$ for any proper subgraph $G_0$ of $G$.
More generally, if $G$ is the $d$-regular infinite tree, then $\mathrm{col}(G)=d+1$, but $\mathrm{col}(G_0)\le d$ for any proper subgraph $G_0$ of $G$.