# Olympiad : The maximum number of pairs whose distance is $1$ when any pairwise distance is at least $1$

Consider the ten points in the plane. Each distance between any two points is larger than or equal to $1$. Then what is the maximum number of pairs whose distance is $1$? I guess that the answer is $19$: Consider the two regular hexagons placed so that the center of each is a corner of the other.

My Trial : As like Dan, I will use the same notations.

Consider the graph such that there exist ten vertices and edges between two vertices has length 1.

Step 1 : The graph is connected.

Proof : If not, we push a component to another component closely. So we can draw another edge. This completes the proof.

Step 2 : Note that any such connected graph has the equality : $v-e + f=1$ where $v$, $e$ and $f$ are the numbers of vertices, edges, and faces respectively.

So $10- e + f =1$ This implies that the maximum of $f$ gives the maximume of $e$.

Consider the graph whose figure is the two regular hexagons placed so that the center of each is a corner of the other.

Note that any vertex in the graph has degree $\geq 3$. This implies that the maximum of $f$ occurs.

-
I edited your post to make it clearer. I hope I did not alter the intended meaning; see the final sentence in particular. – Harald Hanche-Olsen Nov 21 '12 at 8:50
Thanks. I agree that your expression is more clear. – HK Lee Nov 21 '12 at 8:57

Well, you are probably right. Here is a plan of a proof.

For convenience, let's build a graph. The set of vertices $V$ will consist of the given ten points. The set of edges $E$ will contain all pairs of vertices at distance $1$ from each other. We need to prove that $|E| < 20$. To do this it will be enough to prove that $$\sum_{v \in V} \deg v < 40,$$ where $\deg v$ is the number of neighbours of vertex $v$. Let's rewrite this a little: $$\sum_{v \in V} (\deg v - 4 ) < 0.$$ Let us call $\deg v - 4$ the "excess degree" of vertex $v$. We need to prove that the sum of all excess degrees is negative.

To do that, let's deal separately with positive and negative excess degrees.

Degrees 5 and 6. For positive excess degrees, it will suffice to show somehow that $$\sum_{v \in V, \deg v > 4} (\deg v - 4) < 6.$$ I can't see a clever short way to prove this, but it can probably be done with some case analysis. First one can deal separately with the case when there is at least one vertex with degree $6$ (this is a very "rigid" situation). Then, if there are no vertices with degree $6$, it's enough to prove that there are at most 5 vertices with degree $5$, and that shouldn't be too hard.

Degrees 0, 1, 2, 3. For negative excess degrees, we can do this a bit more elegantly. Let us look at any vertex $v$ that is also a corner of the convex hull of set $V$. Let $\angle v$ be the value of this angle of the convex hull (considered as a polygon, not a set). It is easy to see that $$\angle v \geqslant 60^\circ (\deg v - 1).$$ From this we know that every corner of the convex hull has negative excess degree. If we add together all these inequalities for all the corners of the convex hull, we get $$180^\circ (m-2) \geqslant 60^\circ \sum_{v\,\textrm{corner}} (\deg v - 1).$$ $v$ in this sum iterates over all the corners of the convex hull, and $m$ is the number of these corners. It's easy to see that the inequality is equivalent to this: $$\sum_{v\,\textrm{corner}} (\deg v - 4) \leqslant -6.$$ Obviously, the bound will still hold if we extend the sum to all vertices with negative excess degrees: $$\sum_{v \in V, \deg v < 4} (\deg v - 4) \leqslant -6.$$

If we combine this with the bound for positive excess, we will get exactly what we wanted.

So, the only weak link here is the bound for positive excess. What I described sounds like a doable thing, but it looks very clumsy. Maybe someone will come up with a way to avoid case analysis there.

-

The pairs give you a planar graph (the shortest intervals cannot intersect). Assume we have 20 pairs. Then, denoting the total number of faces by $A$, we get $10+A-20=2$ by Euler, so $A=12$. However, we also have $2\cdot 20\ge 3A_3+4\cdot(12-A_3-1)+Q$ where $A_3$ is the number of triangles and $Q$ is the number of boundary edges for the unbounded face. Thus, we must have $Q\le A_3-4$, $A_3\le 11$. On the other hand, $Q$ unit intervals can bound at most $\frac 1{\pi\sqrt 3}Q^2$ triangles, so $(A_3-4)^2\ge \pi\sqrt 3 A_3>5A_3$ which is impossible for $A_3\le 11$.

-
$10+ A -20 =1$ ? Why $10+ A -20 =2$ ? Since it is on the plane so I think that $1$ is right. – HK Lee Nov 21 '12 at 12:03
I count the unbounded face as well. – fedja Nov 21 '12 at 15:29
I see. Thank you. – HK Lee Nov 21 '12 at 16:24