Complete spolier: There's a much simpler solution. The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color (the distance between the two furthest points of the rhombus). So, why not make an isosceles triangle whose two long edges are that length, and whose short edge is length d? Then all three vertices must be the same color, two of which are separated by d. Problem solved. You can obtain this configuration with individual vertices using a mere 7 vertices: Two rhombuses joined at one end, with the opposite ends separated by distance d. I find this graph simpler and more intuitive than the 10-vertex graph from the wiki page. Alternatively, consider the circle of radius sqrt(3)*d. All points on the circle must be the same color as the center, and hence each other. Now draw a chord of length d on the circle. You can think of the rhombus as a compass of radius sqrt(3)*d. I first saw this problem as an interview question years ago. Tom Joerg Arndt writes:
* Tom Karzes <karzes@sonic.net> [Apr 03. 2013 08:34]:
Spoilier spoiler:
Place two equilateral triangles edge-to-edge, and consider the properties of the resulting rhombus.
That was the first thing I tried, but the configuration
B R R G
suggests "no fish" to me: the distance R--R is unequal to the distances R--g and R--B, a case of "either d or sqrt(3)/2*d" (if I got the constant right).
However, Charles' pointer to http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane (especially the image "Solomon W. Golomb's ten-vertex four-chromatic unit distance graph") convinces me (3-color wise).
Given the problem has a name (and having been considered by heavy duty mathematicians) I consider myself only semi stupid now.
Thanks everybody! Best, jj