Задача
COM-B2-M01-P019 Много путей длины два
В графе \(n\) вершин и \(m\) рёбер. Докажите, что число путей длины \(2\) не меньше \(n\binom{\frac{2m}{n}}{2}\), где \(\binom{x}{2}=\frac{x(x-1)}2\). Объясните, почему из этого следует: если средняя степень больше \(r\), то найдётся вершина, через которую проходит больше \(\binom r2\) путей длины \(2\).
Используйте выпуклость функции \(\binom{x}{2}\) и формулу \(\sum d_i=2m\).
Число путей длины \(2\) равно \(\sum_i\binom{d_i}{2}\), где \(d_i\) — степени вершин. Функция \(\binom{x}{2}=\frac{x(x-1)}2\) выпукла, поэтому при фиксированной сумме \(\sum d_i=2m\) сумма \(\sum\binom{d_i}{2}\) не меньше \(n\binom{2m/n}{2}\). Если средняя степень \(\frac{2m}{n}>r\), то среднее значение \(\binom{d_i}{2}\) больше \(\binom r2\) в подходящем строгом смысле, значит некоторая вершина даёт больше \(\binom r2\) путей длины \(2\).
Эта задача требует аккуратного разговора о выпуклости; можно заменить на сглаживание степеней.