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)$?

  • $\begingroup$ It is the minimal degree - sorry, I should have included this in the post, will do. $\endgroup$ Nov 1, 2017 at 14:11
  • $\begingroup$ Are $H$ restricted to be finite subgraphs? $\endgroup$ Nov 1, 2017 at 14:22
  • 7
    $\begingroup$ A line infinite in both directions seems to be a counterexample. $\endgroup$ Nov 1, 2017 at 14:36
  • 2
    $\begingroup$ The comment from @EmilJeřábek should probably be an (accepted) answer, so that the stackexchange software doesn't count this question as unanswered. $\endgroup$ Nov 1, 2017 at 16:36

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.