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?
Best Answer
No.
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.