For $n$ points on a plane, prove that there are at most $3n$ pairs of vertices with distance 1

Question

Question: Given $n$ points in a plane, the distance between any $2$ vertices is at least $1$. Prove there are at most $3n$ pairs of points with distance of exactly $1$.

I've seen this thread, which looks very very similar: Given n points in the plane, such that the minimal euclidian distance is 1, show that there are at most 3n pairs of points with distance exactly 1

However it is about planar graphs - and we did not study what is a planar graph yet (and we won't in the future) Is there a way to solve it without using properties of planer graphs?

I did not understand how to start the proof without using planar graphs theory.. Thank you!

Answer 1

Sure, you can prove this without any graph theory at all.

Suppose there are more than $3n$ distances of length 1. This means more than 6 such distances per point (each distance is a distance between two points, hence it counts twice). This in turn means at least one point with at least 7 neighbors at distance 1, which themselves are at least 1 apart. And that just can't be done, regular hexagon is my witness.

So it goes.

Answer 2

Let $G(V,E)$ be a graph consisting of the $n$ points as vertices, where two vertices are joined by an edge if and only if they are exactly at distance $1$ from one another. We claim that each vertex has degree at most $6$.

To show this, for each vertex $u$, let $v_1$, $v_2$, $\ldots$, $v_k$ be the neighbors of $u$ arranged in the counterclockwise order with $u$ at the center. Because the distance $\overline{v_jv_{j+1}}$ is at least $1$, we conclude that $$\angle v_juv_{j+1}\geq \dfrac{\pi}{3}\,.$$ (Angles are measured counterclockwise.) Therefore, $$2\pi=\sum_{j=1}^k\,\angle v_j uv_{j+1}\geq k\left(\frac{\pi}{3}\right)\,,$$ where $v_{k+1}:=v_1$. Thus, $k\leq 6$.

Therefore, every vertex of $G$ has degree at most $6$. By the Handshaking Lemma, $$|E|= \dfrac{1}{2}\,\sum_{v\in V}\,\deg(v)\leq \dfrac12\,\sum_{v\in V}\,6=3n\,.$$ This bound seems very weak. I expect a better bound to be $$|E|\leq 3n-\mathcal{O}\big(\sqrt{n}\big)\,.$$ I also conjecture that $$|E|\leq 3n-2\sqrt{3n}+o\big(\sqrt{n}\big)\,.$$