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

Задание 30

Для определения числа рёбер в графе воспользуемся теоремой о рукопожатиях: сумма степеней всех вершин графа равна удвоенному числу рёбер.

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

• Сумма степеней = \( 2 + 2 + 3 + 3 + 4 + 4 = 18 \).
• Согласно теореме, \( 2 \times (\text{число рёбер}) = 18 \).
• Число рёбер = \( 18 / 2 = 9 \).

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

• Сумма степеней = \( 0 + 1 + 2 + 2 + 3 + 4 = 12 \).
• Согласно теореме, \( 2 \times (\text{число рёбер}) = 12 \).
• Число рёбер = \( 12 / 2 = 6 \).

Ответ: a) В этом графе 9 рёбер. б) В этом графе 6 рёбер.