Does this proof that $\chi(\mathbb{Q}^2) = 2$ rely on choice?

Question

I'm teaching a course on discrete math and came across a paper related to the Hadwiger-Nelson problem. The question asks how many colors are needed to color every point in $\mathbb{Q}^2$ such that no two points at distance one are the same color.

The proof given in the paper works as follows. First, it defines an equivalence relation over $\mathbb{Q}^2$ where two points are related if the differences of their coordinates can be written with odd denominators. Next, it shows how to color the equivalence class containing the origin with two colors so that no two points at distance one are the same color. Finally, it argues that this coloring can be translated to the other equivalence classes, giving a 2-coloring.

My question is whether this last step - arguing that the coloring can be translated to the other equivalence classes - requires the axiom of choice. I suspect that it does because translating the coloring would require some way to identify which equivalence class a particular point is in and then using that to define the color, but I'm not entirely sure.

Does this result rely on choice? If so, if we reject the axiom of choice, is the chromatic number still two? Or does it change?

Answer 1

There is no actual use of the axiom of choice. Since $\Bbb Q^2$ is a countable set, we can enumerate it and identify each equivalence class with the least-indexed point in that class.

Generally if $X$ can be well-ordered, then there is no need to use the axiom of choice in order to choose from equivalence classes defined on $X$.

Answer 2

It does not require choice. It is true that you have to pick an isometry from each equivalence class to the equivalence class containing the origin. This can be done by translating some chosen point in the equivalence class to the origin. You can do this constructively by well-ordering $\mathbb Q^2$ and choosing the least element. (Note that it is easy to explicitly construct a well-ordering of $\mathbb Q^2$.)