# Chromatic number of the plane

The unit distance graph on has edges between those pairs of points at Euclidean distance .  The chromatic number of this graph lies between (by exhibiting a small subgraph on vertices with chromatic number ) and (by an explicit colouring based on a hexagonal tiling of the plane).  Aubrey de Grey has just posted a construction of a unit distance graph with chromatic number , raising the lower bound on by This MathOverflow post is a good jumping off point into the discussion online.

I was explaining this problem to a colleague and they asked whether this graph was connected (it is) and whether that was still true if we restricted to rational coordinates.  It turns out this was addressed by Kiran B.Chilakamarri in 1988, and the answer is the rational unit distance graph is connected from dimension onwards.

To see that is not connected, consider a general unit vector where is coprime to .  Then .

Claim. is divisible by at most once.

Proof. Squares mod are either , or .  If is divisible by then one of the is odd, hence squares to mod .  But then cannot be divisible by , which is a contradiction.

So the entries of in their reduced form do not contain any ‘s in their denominator, and so the same must hold for all sums of unit vectors.  Hence we can’t express, say, as a sum of unit vectors, and is not connected to .

Connectedness in dimension (hence also later) uses Lagrange’s theorem on the sums of four squares.  We’ll show that can be expressed as a sum of unit vectors.  By Lagrange’s theorem, write .  Then hence is a sum of unit vectors.