1. Степень вершины

Степень вершины — это число рёбер, которые из неё выходят (или, в простом графе, число соседей).

2. Главное правило

Сумма степеней всех вершин графа равна удвоенному числу рёбер:

сумма степеней = 2 · (число рёбер)

Почему: каждое ребро имеет два конца, поэтому в общую сумму степеней вклад каждого ребра равен 2.

3. Алгоритм

а) Запиши, сколько вершин какой степени дано.

б) Посчитай сумму степеней: (число вершин) · (их степень) для каждой группы, затем сложи.

в) Раздели сумму на 2 — получишь число рёбер.

4. Пример

7 вершин степени 4 и 6 вершин степени 3.

Сумма степеней: 7 · 4 + 6 · 3 = 28 + 18 = 46.

Число рёбер: 46 : 2 = 23.

5. Проверка

Сумма степеней всегда должна получиться чётной. Если нечётная — где-то ошибка в расчёте.