
Problem 10.3. Consider $n$ points in the plane such that no three lie on a line. What is the least number of segments having their ends in the given points such that for any two points $A$ and $B$ there exists a point $C$ connected to both $A$ and $B$ ?

Emil Kolev


Solution: Denote the points by $A_{1}, A_{2}, \ldots, A_{n}$. Draw segments connecting $A_{1}$ with all remaining points. Also, draw segments $A_{2} A_{3}$, $A_{4} A_{5}, \ldots, A_{n-1} A_{n}$ when $n$ is odd and $A_{2} A_{3}, A_{4} A_{5}, \ldots, A_{n-2} A_{n-1}$, $A_{2} A_{n}$ when $n$ is even. It is easy to see that the condition of the problem is met and that there are $\left\lceil\frac{3 n-3}{2}\right\rceil$ segments ( $\lceil M\rceil$ denotes the least natural number which is greater or equal to $M$ ).

Suppose it is possible to draw less than $\left\lceil\frac{3 n-3}{2}\right\rceil$ segments and to meet the condition of the problem. Obviously each point is connected by a segment with another one. If each point is connected to at least three others, we will have that the number of segments is at least $\frac{3 n}{2}$, which is greater than $\left\lceil\frac{3 n-3}{2}\right\rceil$. Therefore there exists a point (let that be $A_{1}$ ) connected with at most two others. If $A_{1}$ is connected to exactly one point (let that be $A_{2}$ ), a point connected to both $A_{1}$ and $A_{2}$ does not exist. Therefore $A_{1}$ is connected to exactly two points (let them be $A_{2}$ and $A_{3}$ ). It is easy to see that $A_{2}$ and $A_{3}$
are connected by a segment. Consider the pairs $A_{1}$ and $A_{i}$ for any $i>3$. It is clear that the point connected to both $A_{1}$ and $A_{i}$ could be either $A_{2}$ or $A_{3}$. In both cases $A_{i}$ is connected to $A_{2}$ or $A_{3}$. Since there are at least two segments from each point $A_{i}, i>3$ then the number of segments from $A_{i}, i>3$ is at least $2(n-3)$. Further, since at least $n-3$ from these points connect some point of $A_{i}, i>3$ with $A_{2}$ or $A_{3}$ (and therefore they are counted once) the total number of drawn segments is at least $3+n-3+\left\lceil\frac{n-3}{2}\right\rceil=\left\lceil\frac{3 n-3}{2}\right\rceil$.

This is a contradiction with the number of drawn segments. Therefore the answer is $\left\lceil\frac{3 n-3}{2}\right\rceil$.
