Let $S$ be a set of $n$ points in the plane, the distance between any two of which is at most one. Show that there are at most $n$ pairs of points of $S$ at distance exactly one.
My attempt on proof:
Construct a graph $G$ in which $2$ vertices are adjacent if and only if their distance is exactly one.
Then graph contains $3$ vertices in the form of equilateral triangle (so, $3$ pairs). I don't know how to generalize this.
Best Answer
Hint 1:
given a point, where is located a point at distance 1 from this point ?
Hint 2:
considering the graph whose vertices are the points, and edges are the pairs of points at distance $1$, if a vertex has degree 3, show that one of its neighbours has degree one.
Hint 3:
once you have a cycle in this graph, can you have an other ?
[Edit, since a full proof was provided and mine was asked for]
I. intersection between unit circles.
If two distinct unit circles $\mathcal{C}_1$ and $\mathcal{C}_2$ intersect, their intersection is made of two points, located on the bisector of the segment joining the centres of the circles. This intersection splits $\mathcal{C}_1$ into two arcs.The arc contained on the side of the bisector which does not contain the center of $\mathcal{C}_1$ is shorter than a semi-circle, and is contained in $\mathcal{C}_2$. The intersection of $k$ unit discs is a convex shape whose boundary is made of arcs from the $k$ circles. Each of these arcs is smaller than a semi-circle, and we will refer to such a shape as a polyarc. Since the discs we will intersect are distinct, there cannot be tangent intersections between their boundaries.
II. If a circle intersects an arc of a polyarc, a corner of the polyarc is outside the circle.
By convexity, the polyarc $\mathcal{P}$ and the circle $\mathcal{C}$ intersect in two points. If $\mathbf{p}_1$ is our intersection, by convexity as well, since all the corners of $\mathcal{P}$ are inside $\mathcal{C}$ the second intersection $\mathbf{p}_2$ is located on the same arc as $\mathbf{p}_1$. The portion of the arc between $\mathbf{p}_1$ and $\mathbf{p}_2$ is shorter than a semi circle, and therefore has to be the portion of the circle defining the arc which lies inside $\mathcal{C}$. Therefore, the two corners of the arc are outside $\mathcal{C}$, which is a contradiction.
III. If a vertex of the graph has valence 3, one of its neighbours has valence 1.
Let us consider $\mathbf{p}_0$ of valence 3, and $\mathbf{p}_1$, $\mathbf{p}_2$ and $\mathbf{p}_3$ its neighbours. Wlog, $\mathbf{p}_2$ is between $\mathbf{p}_1$ and $\mathbf{p}_3$ on the circle centered at $\mathbf{p}_0$. The polyarc resulting from the intersection of the discs of $\mathbf{p}_0$, $\mathbf{p}_1$ and $\mathbf{p}_3$ has 3 corners, and $\mathbf{p}_0$ is one of them. If $\mathbf{p}_2$ has a neighbour $\mathbf{p}_4$, the circle $\mathcal{C}$ centred at $\mathbf{p}_4$ passes through $\mathbf{p}_2$ and cuts an arc of the polyarc at this point. From II, one of the corners of the polyarc lies outside the circle, and this cannot be $\mathbf{p}_0$. Therefore half of the arc containing $\mathbf{p}_2$ is outside $\mathcal{C}$, and either does $\mathbf{p}_1$ or $\mathbf{p}_3$, which is a contradiction.
IV. There can be only one cycle
All the vertices of a cycle have valence at least 2, and are therefore corners of the polyarc. In addition, from II, adding a new vertex can only increase the number of corners of the polyarc by 1. Therefore the polyarc has no other corners than the vertices of the cycle. If a new vertex $\mathbf{p}_1$ is added strictly inside the polyarc and has a neighbour $\mathbf{p}_2$, the circle centered at $\mathbf{p}_2$ passing through $\mathbf{p}_1$ intersects the polyarc and a corner of the polyarc is outside this circle, which is a contradiction. $\mathbf{p}_1$ is therefore located on the boundary of the polyarc, and one of the corners is among its neighbours. Since the corners all have valence at least 2, $\mathbf{p}_1$ has valence 1 and cannot be part of a cycle. There is therefore only one cycle. If we have a cycle, cutting an edge of the cycle transforms the graph into a tree which has at $n-1$ vertices. Otherwise, the graph is a forest and has less than $n$ vertices.