Pairs of points exactly $1$ unit apart in the plane This is a problem I found in a graph theory text, but I can't figure it out.
Let $S$ be a set of $n$ points in a plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of $S$ at distance exactly one.
Experimenting, I figured the way to get the most points of distance exactly 1 would be to lay out the points in a grid made out of equilateral triangles. While building up this grid, it seems that when adding a new vertex, I can connect it to 2 or 3 other points to have distance exactly 1, which implies that I can only add at most 3 new pairs of points 1 unit apart for every point I add, which suggests the result. Is there a nonhandwavey way to show this?
 A: Each point can have at most $6$ neighbours at distance $1$, so it can be in at most $6$ pairs. Each pair contains $2$ points. So there can be at most $6n/2=3n$ such pairs.
A: It's natural (especially since this is a graph theory text...) to turn the set $S$ into a graph by connecting two points (vertices) if they are exactly one unit apart. What can you say about this graph? Can you say something about the degrees of the vertices? What, in terms of this graph, are you trying to prove?
A: Define $G(V, E)$ such that $V$ contains all the points and $(u, v) \in E$ iff $u, v$ are exactly one unit of distance apart.
Given $\sum_{v \in V} d_v = 2 |E|$, showing that there are at most $3n$ pairs with distance 1 is equal with
$$ \sum_{v \in V} d_v \leq 6n $$
Now, assume $\sum_{v \in V} d_v > 6n$. Then there exists at least one vertex $v$ such that $d_v > 6$. Observe that any 2 vertices must be at least one unit of distance apart. The most number of vertices you can keep at a distance of 1 around $v$ is 6, using triangle geometry.
Assume there are 7 points $u_1, \cdots, u_7$ on the circumference of a circle with radius 1 around $v$. Then there exist $u_i, u_j$ such that $\angle u_i v u_j < 60^\circ$; you have an equilateral triangle where two edges are one unit long and exactly one angle is less than 60 degrees, so the third edge ($u_iu_j$) is less than one unit long (use one of the triangle inequalities). This contradicts what we assume in the problem description.
