Придумайте и нарисуйте 3 неодинаковых графа, в каждом из которых по 6 рёбер. Найдите сумму степеней всех вершин каждого из этих графов.

128. **Ответ: Сумма степеней вершин каждого графа равна 12.** Согласно лемме о рукопожатиях, сумма степеней вершин графа всегда равна удвоенному числу его рёбер. Так как в каждом графе по 6 рёбер, сумма степеней будет: $$2 \cdot 6 = 12$$ Примеры таких графов: 1. Цикл из 6 вершин ($C_6$): каждая вершина имеет степень 2. Сумма: $2+2+2+2+2+2 = 12$. 2. Звезда: одна центральная вершина со степенью 6 и 6 висячих вершин со степенью 1 (итого 7 вершин). Сумма: $6 + 1 \cdot 6 = 12$. 3. Две несвязанные части: треугольник (3 вершины степени 2, итого 3 ребра) и ещё один треугольник (3 вершины степени 2, итого 3 ребра). Всего 6 рёбер. Сумма: $2 \cdot 6 = 12$. 129. **Доказательство:** Каждое ребро графа соединяет две вершины (или является петлёй, входящей в одну вершину дважды). При подсчёте суммы степеней вершин каждое ребро учитывается ровно два раза — по одному разу для каждой из двух вершин, которые оно соединяет. Следовательно, сумма степеней всех вершин равна числу рёбер, умноженному на 2. $$\sum_{v \in V} deg(v) = 2|E|$$ 130. Чтобы найти количество рёбер, нужно сложить степени всех вершин и разделить полученную сумму на 2. а) Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$. Количество рёбер: $18 : 2 = 9$. **Ответ: 9 рёбер.** б) Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$. Количество рёбер: $12 : 2 = 6$. **Ответ: 6 рёбер.**