130 В некотором графе 6 вершин, степени которых равны: a) 2, 2, 3, 3, 4, 4; б) 0, 1, 2, 2, 3, 4. Сколько всего рёбер в этом графе?

Решение:

В теории графов существует основная теорема: сумма степеней всех вершин графа равна удвоенному количеству рёбер. Это означает, что если мы просуммируем степени всех вершин, а затем разделим полученную сумму на 2, то получим количество рёбер в графе.

а) Степени вершин: 2, 2, 3, 3, 4, 4

Сумма степеней = $$2 + 2 + 3 + 3 + 4 + 4 = 18$$.

Количество рёбер = Сумма степеней / 2 = $$18 / 2 = 9$$.

б) Степени вершин: 0, 1, 2, 2, 3, 4

Сумма степеней = $$0 + 1 + 2 + 2 + 3 + 4 = 12$$.

Количество рёбер = Сумма степеней / 2 = $$12 / 2 = 6$$.

Ответ: а) 9 рёбер; б) 6 рёбер.