3 стороны треугольника

[daogiauvang]

Дано $n$ точек на поверхности, чтобы не существуют $3$ любые точки на одной прямой. Соединив $[\frac{n^2}{4}] +1$ отрезков, доказать, что из полученных отрезков есть 3 отрезка являются сторонами треугольника.

[DeBill]

Пусть нет треугольников.
Пусть $A$ - вершина максимальной степени, $S$ - смежные с ней, , $N$ - не смежные с ней, $\left\lvert S \right\rvert =d$.
Тогда ребер не более $d$ (из $A$) $+ d\cdot (n-d-1)$ (все прочие выходят из $N$, а степень вершин не превышает $d$ ) $= d(n-d)$. При четном $n=2k$ это не более $k^2$, при нечетном $n = 2k+1$ - не более $k(k+1)$. Противоречие.
Оценка точная: для двудольного графа с равными (почти) долями имеем равенство.