Задача
COM-B2-M01-P007 Большая степень
#7
★★★☆☆ Уровень 3 из 5
В простом графе \(n\) вершин и больше \(\frac{(r-1)n}{2}\) рёбер. Докажите, что найдётся вершина степени хотя бы \(r\).
Используйте сумму степеней.
Сумма степеней равна \(2E>(r-1)n\). Если бы все степени были не больше \(r-1\), сумма степеней была бы не больше \((r-1)n\), противоречие. Значит, есть вершина степени хотя бы \(r\).
Базовая форма “среднее больше \(r-1\)”.