Axiom of choice and chromatic number: Examples on the plane (Q598462)

Let the vertices of the graph \(G_2\) be \({\mathbb R}^2\) with \(x\) and \(y\) joined iff \(x-y\in {\mathbb Q}^2+a\) where \(a\) is either \((\sqrt{2},0)\), \((0,\sqrt{2})\), \((\sqrt{2},\sqrt{2})\), or \((-\sqrt{2},\sqrt{2})\). It is shown that if the axiom of choice holds then the chromatic number of \(G_2\) is 4. If, however, the countable axiom of choice holds and every set of reals is Lebesgue measurable then, by Steinhaus's theorem, \(G_2\) is not even countably chromatic. A similar argument works if \(x\) and \(y\) are joined iff \(x-y\in {\mathbb Q}^2+\bigl\{(\sqrt{2},0),(0,\sqrt{2})\bigr\}\)