I guess I wasn't explicit enough about the proof strategy. I'll try to state it more completely. Assume, for a given d, and for some 3-coloring of the plane, that all points separated by distance d are different colors. Then try to prove a contradiction, i.e. that there must exist two points separated by distance d that are in fact the same color. If you can do that, then the original assummption must be false. Which in turn implies that there exists no 3-coloring of the plane for which all points separated by distance d are separate colors. The claim I made about all points separated by distance sqrt(3)*d being the same color must be true if in fact all points separated by distance d are different colors, as you said. It is a logical implication of that assumption. But that implication can be used to show that the original assumption cannot hold. So yes, once we reach a contradiction, we know that all points separated by distance d are not different colors, and therefore that all points separated by distance sqrt(3)*d may not be the same color. I.e., the entire chain of implications breaks down. Since the original assumption is seen to be false, then everything that follows from it is suspect. But at that point it no longer matters. That's how proof by contradication works, yes? As I described, this leads to a simpler 7-vertex graph, with a more intuitive approach to its construction, than the 10-vertex graph on the wiki page. I'd include it here, except I don't think ascii art will suffice. But it should be clear that this graph cannot be 3-colored without two connected vertices being the same color. Tom Cris Moore writes:
On Apr 3, 2013, at 3:09 AM, Tom Karzes wrote:
The rhombus construct I suggested implies that any two points separated by sqrt(3)*d must be the same color
I don't think that follows: that's only the case if all pairs of points at distance d are different colors.
But the rhombus does show that, for every d, either there is a pair at distance d or a pair at distance sqrt(3)d with the same color (in any 3-coloring).
The unit-distance graphs (like Moser's and Golomb's) on Wikipedia is interesting:
http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
But if all distance graphs are 4-colorable, then this technique can't raise the lower bound on the chromatic number of the plane beyond 4. Does anyone know if that's the case? (Note that not all unit-distance graphs are planar.)
Cris