Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let two distinct functions $f,g:\mathbb{N}\to\mathbb{N}$ form an edge if and only if they differ in exactly one input $n\in\mathbb{N}$.


Let $G=(V,E)$. Clearly, $G$ has cliques of cardinality $\aleph\_0$. Is $\chi(G) = \aleph\_0$?



Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$
Yes, $\chi(G) = \aleph\_0$. To see this, define $f \sim g$ if $\{n : f(n) \not= g(n) \}$ is finite. $\sim$ is an equivalence relation, all equivalence classes of $\sim$ are countable, and $\{f,g\} \in E \Rightarrow f \sim g$. (In fact, the equivalence classes of $\sim$ are precisely the connected components of $G$.) Thus, we can color $G$ with countably many colors simply by ensuring that, if $f$ and $g$ are in the same equivalence class, they are given different colors.


