Find the largest integer such that the following holds: there exists a set of points in the plane such that, for any choice of three of them, some two are unit distance apart.
Solution
We can obtain in the following way: Consider a rhombus made up of two equilateral triangles of side length 1 , where . Rotate the rhombus clockwise about to obtain a new rhombus such that . Then one can verify that the seven points satisfy the problem condition. To prove that points is unobtainable, one interprets the problem in terms of graph theory. Consider a graph on 8 vertices, with an edge drawn between two vertices if and only if the vertices are at distance 1 apart. Assume for the sake of contradiction that this graph has no three points, no two of which are at distance 1 apart (in terms of graph theory, this means the graph has no independent set of size 3). First, note that this graph cannot contain a complete graph of size 4 (it's clear that there can't exist four points in the plane with any two having the same pairwise distance). I claim that every vertex has degree 4 . It is easy to see that if a vertex has degree 5 or higher, then there exists an independent set of size 3 among its neighbors, contradiction (one can see this by drawing the 5 neighbors on a circle of radius 1 centered at our initial vertex and considering their pairwise distances). Moreover, if a vertex has degree 3 or lower then there are at least four vertices that are not at distance 1 from that vertex, and since not all four of these vertices can be at distance 1 from one another, there exists an independent set of of size 3, contradiction. Now, we consider the complement of our graph. Every vertex of this new graph has degree 3 and by our observations, contains no independent set of size 4. Moreover, by assumption this graph contains no triangle (a complete graph on three vertices). But we can check by hand that there are only six distinct graphs on eight vertices with each vertex having degree 3 (up to isomorphism), and five of these graphs contain a triangle, and the remaining graph contains an independent set of size 4, contradiction! Hence the answer is