Изобразите три разных графа, у которых четыре ребра, четыре вершины. Найдите сумму степеней вершин каждого графа.

Для решения задачи вспомним, что степень вершины — это количество рёбер, выходящих из неё. Согласно лемме о рукопожатиях, сумма степеней всех вершин графа всегда равна удвоенному количеству его рёбер. Так как в каждом графе по 4 ребра, сумма степеней для любого такого графа будет: $4 \times 2 = 8$. Варианты графов с 4 вершинами и 4 рёбрами: 1. **Цикл ($C_4$):** Вершины соединены в кольцо (квадрат). Степени вершин: 2, 2, 2, 2. Сумма: $2+2+2+2 = 8$. 2. **Треугольник с «хвостом»:** Три вершины образуют треугольник, а четвёртая соединена с одной из них. Степени вершин: 3 (узел), 2, 2, 1 (конец хвоста). Сумма: $3+2+2+1 = 8$. 3. **Граф с кратными рёбрами или петлёй (если допустимо):** Например, путь из трёх рёбер и одна петля у вершины. Если рассматривать только простые графы, то третьим вариантом может быть «все вершины связаны с одной центральной + одно ребро между боковыми» (в данном случае при 4 вершинах это будет топология, похожая на треугольник с висячим ребром, описанный выше). Другой вариант — две пары вершин, соединённые параллельными рёбрами (мультиграф). Для простого графа с такими параметрами также подходит структура «звезда» с одним дополнительным ребром. **Ответ: Сумма степеней вершин каждого графа равна 8.**