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

128. Придумайте и нарисуйте 3 неодинаковых графа, в каждом из которых по 6 рёбер. Найдите сумму степеней всех вершин каждого из этих графов. Согласно лемме о рукопожатиях, сумма степеней всех вершин любого графа равна удвоенному числу его рёбер. Если в графе 6 рёбер, то сумма степеней всегда будет одинаковой для любого такого графа. **Ответ: Сумма степеней всех вершин каждого из графов равна 12.** Примеры графов с 6 рёбрами: 1. Цикл из 6 вершин ($C_6$): каждая вершина имеет степень 2. $2 \times 6 = 12$. 2. Звезда ($S_7$): 1 центральная вершина (степень 6) и 6 висячих вершин (степень 1). $6 + 1 \times 6 = 12$. 3. Две несвязанные части: треугольник ($C_3$, 3 ребра, сумма степеней 6) и ещё один треугольник ($C_3$, 3 ребра, сумма степеней 6). Итого $6 + 6 = 12$. 129. Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер в этом графе. **Доказательство:** Каждое ребро графа соединяет две вершины (или является петлёй, которая входит в одну вершину дважды). При подсчёте суммы степеней всех вершин мы считаем, сколько концов рёбер входит в каждую вершину. Так как у каждого ребра ровно 2 конца, при суммировании степеней всех вершин каждое ребро будет учтено ровно 2 раза. Таким образом, сумма степеней всех вершин равна $2E$, где $E$ — количество рёбер. 130. В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 4, 4; Проверим возможность существования такого графа с помощью суммы степеней: $$\sum deg(v) = 2 + 2 + 3 + 3 + 4 + 4 = 18$$ Сумма степеней чётная (18), и количество нечётных вершин (две тройки) также чётно. Это удовлетворяет лемме о рукопожатиях. Число рёбер в таком графе было бы: $18 : 2 = 9$. **Ответ: Граф с такими степенями вершин существовать может.**