Graphing problem Let $n ≥ 3$ be an integer, and let $S$ be a set of $n$ points on the plane such that the distance between any pair of points in $S$ is at least 1. Prove that there exists at most $3n - 6$ pairs of points where the distance is exactly $1$.
How would I solve this problem? :\
 A: Hint:


*

*For any planar graph with $n \geq 3$ vertices we have that it has at most $3n-6$ edges:

*

*this is due to Euler's formula: $|V| − |E| + |F| = 2$, where $V$ are the vertices, $E$ are the edges and $F$ are the faces,

*each face has at least 3 edges, and every edge belongs to at most two faces,

*$|V|-|E|+\frac{2}{3}|E| \geq 2$, that is $3|V|-6 \geq |E|$.


*If we were to put an edge between every pair of vertices between which the distance is 1, then we would get a planar graph (there cannot be any crossing edges, because the smallest distance allowed is 1).


I hope this helps $\ddot\smile$
A: For a set of $n$ points, $n\ge 3$, the most number of pairs of points that have distance exactly one is:
$$\lfloor 3n-\sqrt{12n-3}\rfloor$$
Starting with $n=3$ this gives values of $3,5,7,9,12,14,16,19,\ldots$.  The sequence is A047932.
Now, notice that the maximum is achieved at $n=3$, and that $$\lfloor 3n-\sqrt{12n-3}\rfloor\le 3n-\sqrt{12n-3}< 3n-6$$ for $n>4$.
You can read more about how the above formula is derived here.
