Какой может быть сумма степеней вершин графа?

Чтобы понять, какая может быть сумма степеней вершин графа, начнем с некоторых определений и основных понятий.

Определения:

1. Граф — это множество вершин, соединённых рёбрами.
2. Степень вершины — это количество рёбер, связанных с данной вершиной.
3. Сумма степеней всех вершин — это общее количество рёбер, учитывая, что каждое ребро соединяет две вершины.

Пошаговое решение:

1. Формула для суммы степеней вершин: В любом графе сумма степеней всех вершин равна удвоенному количеству рёбер. Это записывается в виде: \[ \sum_{v \in V} \text{deg}(v) = 2E \] где:

   • \( \sum_{v \in V} \text{deg}(v) \) — сумма степеней всех вершин,
   • \( E \) — количество рёбер в графе.

2. Почему формула работает? Каждое ребро соединяет две вершины, таким образом при подсчёте степеней вершин каждое ребро учитывается дважды — для каждой из соединённых вершин. Например, если есть рёбра между вершинами A и B, то степень вершины A увеличится на 1, и степень вершины B также увеличится на 1.

3. Примеры:

   • Рассмотрим граф с 3 вершинами и 3 рёбрами, где каждая вершина соединена с двумя другими:
     • Степени вершин будут: 2, 2 и 2.
     • Сумма степеней: \( 2 + 2 + 2 = 6 \).
     • Количество рёбер: 3.
     • Проверка: \( 2E = 2 \cdot 3 = 6 \).
   • Если у нас есть граф с 4 вершинами и 2 рёбрами:
     • Степени вершин могут быть: 1, 1, 0, 0 (две вершины соединены между собой, и два других не имеют соединений).
     • Сумма степеней: \( 1 + 1 + 0 + 0 = 2 \).
     • Количество рёбер — 2, что также соответствует \( 2 = 2 \cdot 1 \).

Заключение:

Сумма степеней вершин графа всегда четное число, так как она равна удвоенному количеству рёбер. Таким образом, сумма степеней может принимать значения 0, 2, 4, 6 и так далее, что в итоге всегда будет чётным числом.