[Math] Pairs of points exactly $1$ unit apart in the plane

combinatoricsgraph theory

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?

Best Answer

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.