Задача
COM-B1-M09-P018 Доля из пяти вершин
#18
★★★☆☆ Уровень 3 из 5
В двудольном графе доли имеют размеры \(5\) и \(7\), а ребер \(20\). Докажите, что в доле из \(5\) вершин есть вершина степени не меньше \(4\).
Посчитайте среднюю степень в этой доле.
Каждое ребро выходит из ровно одной вершины доли размера \(5\). Поэтому сумма степеней вершин этой доли равна \(20\). Средняя степень равна \(20/5=4\). Значит хотя бы одна вершина имеет степень не меньше \(4\).
Среднее в одной доле часто сильнее общего среднего.