The following question was asked in a comment by Joel David Hamkins in [Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$](https://mathoverflow.net/questions/207181/graph-on-the-set-of-all-functions-f-mathbbn-to-mathbbn).


Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let $$E:=\big\{\{f,g\}: f, g \in V \land f\neq g\land \exists k\in \mathbb{N} \text{ }\forall n\in\mathbb{N}\setminus\{k\} (f(n) = g(n))\big\}.$$


Let $G=(V,E)$. This graph is Borel. Can there be a [Borel $\mathbb{N}$-coloring](https://jaywillmath.wordpress.com/tag/borel-chromatic-number/)?



Borel coloring of a graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$
I claim that there can be no Borel $\mathbb{N}$-coloring of this graph. 


To see this, suppose toward contradiction that there is such a Borel coloring. 
Consider the forcing to add a generic Cohen real, in the form of a
function $g:\mathbb{N}\to\mathbb{N}$. So the forcing conditions
are finite partial functions from $\mathbb{N}\to\mathbb{N}$,
ordered by extension. Since the coloring has a Borel code, we may
interpret this code in the forcing extension $V[g]$ (where I use $V$ here as usual to denote the original set-theoretic universe, rather than your use to denote the underlying set of the graph $\mathbb{N}^{\mathbb{N}}$). Furthermore,
the interpretation of that coloring is still a coloring of the
corresponding graph as defined in the forcing extension $V[g]$,
since the assertion that a given Borel code codes a coloring for
that graph is a $\Pi^1\_1$ assertion and hence absolute between the
universe $V$ and the forcing extension $V[g]$. So the generic
function $g$ gets some color, say $k$. This fact must be forced by
some finite piece of the generic function $p=g\upharpoonright n$.
That is, condition $p$ forces that the generic function gets color
$k$. But now let us modify $g$ to form a new function $g'$ by
making a single change beyond $p$. So $g'$ is also generic, and
furthermore extends $p$, and the corresponding forcing extensions
are the same $V[g]=V[g']$. It follows that $g'$ must also get
color $k$, since this was forced by $p$, and this contradicts the
fact that $g$ and $g'$ are adjacent in the graph. So there can be
no such coloring. **QED**


This argument is similar to an argument showing that almost-equality has no Borel selector, and a similar idea appears in [this MO question}(<https://mathoverflow.net/a/47191/1946>) concerning the non-existence of a Borel diagonalization against countable sets of reals.


