Problem 11.3. Consider a set $S$ of 2006 points in the plane. A pair $(A, B) \in$ $S \times S$ is called "isolated" if the disk with diameter $A B$ does not contain other points from $S$. Find the maximum number of "isolated" pairs.

Alexander Ivanov
11.3. Consider a graph with vertices the given points. Two points form an edge if the corresponding pair of points is "isolated". We first prove that the graph is connected. To do this suppose that it has more than one connected component and chose points $A$ and $B$ from different components such that the distance $A B$ is the least possible. Then the disk with diameter $A B$ does not contain other vertices and therefore $A$ and $B$ are connected by an edge. This contradicts the choice of $A$ and $B$.

Since a connected graph with 2006 vertexes has at least 2005 edges (if the graph is a tree) we conclude that there are at least 2005 "isolated" pairs.

If we take 2006 points on a semicircle such that the distances between consecutive points are equal then "isolated" are only the pairs of neighboring points. Therefore there are 2005 "isolated" pairs.