4ВПР →

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

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

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



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

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

Теория

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

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

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