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

Для решения задачи воспользуемся «Леммой о рукопожатиях»: сумма степеней всех вершин графа всегда в два раза больше количества его рёбер. Это происходит потому, что каждое ребро соединяет две вершины и, следовательно, учитывается дважды при подсчёте степеней. ### 1. Примеры трёх неодинаковых графов с 6 рёбрами: 1. **Граф-цикл ($C_6$):** 6 вершин соединены последовательно в кольцо. У каждой вершины степень 2. Сумма степеней: $2+2+2+2+2+2 = 12$. 2. **Звёздный граф ($S_7$):** 1 центральная вершина и 6 «лучей» к другим вершинам. Степень центральной вершины — 6, остальных шести — по 1. Сумма степеней: $6 + (1 \times 6) = 12$. 3. **Путь ($P_7$):** 7 вершин соединены последовательно в одну линию. Две крайние вершины имеют степень 1, остальные пять — степень 2. Сумма степеней: $(1 \times 2) + (2 \times 5) = 12$. ### 2. Сумма степеней вершин Для любого графа с 6 рёбрами сумма степеней всех его вершин всегда будет равна: $S = 2 \cdot E = 2 \cdot 6 = 12$ Где $E$ — количество рёбер. ### 3. Доказательство **Утверждение:** Сумма степеней всех вершин графа вдвое больше числа рёбер. **Доказательство:** Каждое ребро графа имеет два конца. При вычислении степени вершины мы считаем количество рёбер, выходящих из неё. Когда мы суммируем степени всех вершин, каждое ребро учитывается ровно два раза — по одному разу для каждой из двух вершин, которые оно соединяет. Таким образом, сумма степеней всех вершин равна $2E$, что и требовалось доказать. **Ответ: 12.**