Пусть всего
точек. Рассмотрим граф на этих вершинах. Рассмотрим вершину (пусть это вершина
) с наибольшей степенью. Пусть эта степень равна
. Заметим, что у вершин, имеющих связь с
нет ребер к другим вершинам, связанным с
(иначе получился бы треугольник). Поэтому степень этих вершин не больше, чем
. Степени оставшихся не превосходят
. Поэтому сумма степеней не превосходит
. Количество ребер не превосходит
(последнее неравенство — следствие из н-ва между ср. арифм. и ср. геометр.)
С другой стороны, несложно привести пример: рассмотрим двудольный граф (две равные доли по 50 вершин) и проведем всевозможные ребра (их будет 50*50=2500).
Если же проведено более 2500 ребер, то образуется хотя бы один треугольник (на самом деле их будет хотя бы 50).
ответ: 2500
Поделитесь своими знаниями, ответьте на вопрос: