Считаем рёбра

Оценка. Зафиксируем натуральное число Рассмотрим в графе все вершины степени Они не соединены между собой, поэтому оставшихся вершин хотя бы Тогда вершин степени не больше, чем Значит, всего рёбер в графе не более, чем

Пример. Разобьём вершин на группы. В первой группе вершина, во второй — вершины, в последней — вершины. Пусть любые две вершины из разных групп будут соединены ребром, а вершины из одной группы — нет. Тогда в первой группе будет одна вершина степени во второй — вершины степени вершины степени Получается, что суммарное количество рёбер вычисляется по формуле из оценки, то есть равно