Олимпиада Туймаада по математике. Старшая лига. 2022 год

В королевстве 100 городов, некоторые пары городов соединены дорогами. Известно, что для любых двух городов $A$ и $B$, соединенных дорогой, найдется город $C$, не соединенный дорогой хотя бы с одним из этих двух городов. Какое наибольшее количество дорог может быть в этом королевстве? ( X. Zhan, P. Qiaoa )

Комментарий/решение

Из условия понятно что у нашего графа нету треугольников. Тогда теоремой Турана для n=<8.

ex(100,3)=[100²×((3-2)/(6-2))]=2500.