# Do we need the axiom of choice for determining the chromatic number of the graph with vertex set $\mathbb{Q}^n$ with forbidden distance equal to $1$?

We have the graph $$G$$ with vertex set $$\mathbb{R}^n$$ ($$n\in \mathbb{N}^*$$) and any two vertices have an edge iff their euclidean distance ist equal to $$1$$. Now any two points with an edge must have different colors. The chromatic number $$\chi$$ of a graph is the smallest number of colors needed to color the graph.

In the two dimensional case ($$n=2$$), the determination of $$\chi$$ is known as the "Hadwiger-Nelson-problem". The "De Bruijn-Erdös theorem" states that we can determine the chromatic numbers of the finite subgraphs of $$G$$ and the maximum of these chromatic numbers is in fact the chromatic number of the graph $$G$$. For this result, the axiom of choice is needed, so I think it is for any dimension $$n \in \mathbb{N}^*$$.

Now my question is, if we look at the similar graph with vertex set $$\mathbb{Q}^n$$ (in fact a subgraph of $$G$$), do we still need the axiom of choice for determining its chromatic number?

Since $$\Bbb Q^n$$ is countable for any finite $$n$$, it is also well-orderable in $$\sf ZF$$. So a graph can be coded by a set of ordinals, $$A$$. Then, in $$L[A]$$, which is the smallest model of $$\sf ZFC$$ in which $$A$$, our set of ordinals, is a member of, the axiom of choice holds, and if we were just a bit careful with how we coded $$\Bbb Q$$ and the graph itself, then that coding is absolute between $$L[A]$$ and "the real" universe, $$V$$.
So we have a model of $$\sf ZFC$$ in which we have that very graph of interest. So if we can prove from $$\sf ZFC$$ that $$\chi$$ is, say, $$5$$, then that holds in $$L[A]$$. Now, if we have any colouring, $$c$$, it too can be coded into a set of ordinals, $$B$$, then in $$L[A,B]$$ we have the both the graph and the colouring and $$\sf ZFC$$ holds.
You can also code the whole thing as a statement about second-order arithmetic, and you can check that the complexity here is no more than $$\Pi^1_2$$ with the graph as a parameter (and I'm just being lazy, this is probably $$\Pi^1_2$$ as a statement about all the graphs), and so by using Shoenfield's absoluteness theorem to $$L[A]$$, as described above, we also get the same result.