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

### Задание 125 **Условие:** Придумайте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3. **Решение:** Сумма степеней вершин равна: $1 + 1 + 2 + 2 + 3 + 3 = 12$. По лемме о рукопожатиях количество рёбер в графе равно половине суммы степеней: $12 : 2 = 6$ рёбер. Чтобы графы были неодинаковыми (неизоморфными), можно по-разному соединить вершины с разной степенью. 1. **Первый вариант:** Составим граф из двух отдельных частей (компонент связности). Одна часть — треугольник (вершины со степенями 2, 2, 2), вторая часть — «звезда» из 3 вершин (одна вершина со степенью 2 в центре и две вершины со степенью 1 на концах). Но нам нужны степени 3. Попробуем иначе. 2. **Второй вариант (связный):** Представь кольцо из 4 вершин (степени 2). Добавим еще 2 вершины. Соединим вершины так, чтобы получились нужные степени. Например, путь из вершин: $V_1(1)-V_2(3)-V_3(3)-V_4(1)$ и добавим цикл $V_2-V_5(2)-V_6(2)-V_3$. **Описание структуры:** * **Граф А:** Вершины со степенью 3 соединены между собой ребром. От каждой из них отходит по одному «хвосту» (вершина степени 1). Оставшиеся две вершины степени 2 образуют с вершинами степени 3 замкнутый цикл. * **Граф Б:** Две вершины степени 3 не соединены друг с другом напрямую, а соединены через общих соседей (вершины степени 2). ### Задание 126 **Условие:** Придумайте 3 неодинаковых графа, в каждом из которых по 6 рёбер. Найдите сумму степеней всех вершин каждого из этих графов. **Решение:** Согласно основной теореме теории графов (лемма о рукопожатиях), сумма степеней всех вершин любого графа всегда равна удвоенному количеству его рёбер. Если в графе 6 рёбер, то сумма степеней его вершин: $$\sum deg(V) = 2 \cdot E = 2 \cdot 6 = 12$$ Это правило верно для любого графа с 6 рёбрами, независимо от его вида. **Примеры 3 неодинаковых графов:** 1. **Цикл ($C_6$):** 6 вершин, соединенных по кругу. У каждой вершины степень 2. Сумма: $2 \cdot 6 = 12$. 2. **Звезда ($S_7$):** Одна центральная вершина соединена с 6 другими. Степень центральной — 6, остальных — по 1. Сумма: $6 + (1 \cdot 6) = 12$. 3. **Полный граф из 4 вершин ($K_4$):** В нем как раз 6 рёбер. У каждой из 4 вершин степень 3. Сумма: $3 \cdot 4 = 12$. **Ответ:** Сумма степеней всех вершин равна 12.