Construct a locally finite graph with infinite chromatic number.

Question

Construct a locally finite graph with infinite chromatic number. I don't think this is possible since the degree of every vertex is finite, and $\chi(G) \le x+1$, where $x$ is maximum degree, but the author says it's possible. How?

Answer 1

Let's think about $\chi(G) \le x+1$ for a moment. Since $x$ is always finite, you would think that $\chi(G)$ is finite as well. But, for instance, say $x=1,2,3,\ldots$ We know that $\chi(G)\le \max(x)+1$... but what is $\max(x)$? If you think about it, this maximum is "infinite", so it's entirely possible for $\chi(G)$ to be infinite as well, and an example of a graph where this is realised is, as PkT says in the comments, a union of finite cliques: consider $K_1,K_2,K_3,\ldots$ Clearly this graph cannot have chromatic number $n$ for any finite $n$, as $n$ colours are insufficient to colour in an $n+1$-clique. Thus this graph has infinite chromatic number.