4ВПР →

В графе 4 вершины имеют степень 3 и 3 вершины — степень 2. Сколько рёбер в графе?

Показать решение

Находим сумму степеней всех вершин:

По лемме о рукопожатиях:

Ответ: 9 рёбер

Теория

1) Сумма степеней всегда чётна (так как равна 2E)
Число вершин нечётной степени всегда чётно
Если при решении получается нецелое число рёбер — граф не существует

2) Проверка существования графа:
Сумма степеней должна быть чётным числом
Каждая степень должна быть неотрицательным целым числом
Максимальная степень вершины в простом графе с n вершинами: deg(v) ≤ n-1

3) Алгоритм решения:
 - Найти сумму степеней всех вершин
 - Разделить на 2
 - Проверить, что результат — целое число
 - Если да — это количество рёбер, если нет — граф не существует