As previous posters pointed out, if you want to color the plane so that any 2 points at distance=1 have different colors than you need at least 4 colors (proof:Moser or Golomb's graphs) while 7 colors are known to suffice (proof: tiling by regular hexagons, each monocolored). http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane I now point out, that if your coloring is required to be PERIODIC and I get to choose the period-parallelogram, then one can prove 7 colors are both necessary and sufficient. Reason is, the tiling of the plane by equilateral triangles, is, in fact, viewed modulo an appropriate period parallelogram, the complete graph K7. Here is a picture drawn by Steven Taschuk: http://amotlpaa.nfshost.com/math/k7torus.html This incidentally also shows that torus graphs can require 7 colors (which also is known to suffice). Meanwhile a hex-tiling construction proves sufficiency. The catch is, that the period-parallelogram for the "necessary" is not the same as for the "sufficient"!