Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.


What is $\chi(G)$?


(This is a variant of the [Hadwiger-Nelson problem](http://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem).)



A variant to the Hadwiger-Nelson problem
By considering all the rational numbers on the $x$-axis we can see that we need at least countably many colors. This is also sufficient, that is the chromatic number of the rational-distances graph is countable. This is due to Erdos and Hajnal in the case of $\mathbb R^2$. They show that the rational-distances graph in the plane does not contain a copy of the complete bipartite graph $K(2,\omega\_1)$, and that any such graph must have countable chromatic number.



> 
> P. Erdos and A. Hajnal, "On chromatic number of graphs and set systems", Acta Math. Hungar. 17(1966), 61-99.
> 
> 
> 


The result was generalized to rational distances graphs in $\mathbb R^n$ by Peter Komjath. However, the previous method doesn't generalize since now the graph contains even a copy of $K(\omega, 2^\omega)$. Instead, Komjath uses a clever transfinite induction argument.



> 
> P. Komjath, ["A decomposition theorem for $\mathbb R^n$"](http://www.ams.org/journals/proc/1994-120-03/S0002-9939-1994-1169038-0/) Proc. Amer. Math. Society (1994): 921-927.
> 
> 
> 


