There are given $n$ points on plane. Prove that there are not more than $n$ pairs of vertices, distance between which is exactly $d$

Question

$\textbf{Source:}$I found this question in aopslink

As you can see in this link it doesn't mention any source either.

$\textbf{Question:}$There are given $n$ points on plane. Let $d$ be the biggest distance between any pair of vertices. Prove that there are not more than $n$ pairs of vertices, distance between which is exactly $d$

I tried to use induction.The base case is obvious.Assuming the result is true for n points,I tried to show that it also holds for $n+1$ points.Now,If I could show that there is one point which makes at most one pair with distance $d$, I would be done.So,assuming otherwise all points is in at least two pair whose distance is $d$.I could not progress any far.

I would appreciate some hint or solution.Thanks in advance

Answer 1

Let $G$ denote the graph on the $n$ vertices, where two vertices share an edge if and only if the distance between them is $d$. Let $k$ denote the number of edges in $G$. We wish to show that $k\leq n$.

Let $G'$ denote the graph obtained by repeatedly removing all vertices $v\in G$ with $\deg v\leq1$, so that the number of edges removed is no greater than the number of vertices removed. Then it suffices to show that $k'\leq n'$, where $n'$ and $k'$ denote the numbers of vertices and edges of $G'$, respectively.

Suppose toward a contradiction that $\deg v\geq3$ for some $v\in G'$. The pairwise distance between the neighbours of $v$ is also at most $d$, and hence all neighbours of $v$ lie on a circular arc of radius $d$ centered at $v$ of at most $\tfrac\pi3$ radians. Let $w_1,w_2\in G'$ be the two neighbours of $v$ that are furthest apart, and $w\in G'$ any other neighbour of $v$. The following image clarifies the situation:

The four circles are centered at $v$, $w_1$, $w_2$ and $w$ and all have the same radius $d$. It follows that all other vertices of $G'$ are contained in the region shaded red. In particular the only vertex in $G'$ at distance $d$ from $w$ is $v$. But then in $G'$ we have $\deg w=1$, a contradiction. This shows that $\deg v=2$ for all $v\in G$ and hence that $k'\leq n'$.