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

Задание 29

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

Доказательство:

Рассмотрим граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер.

Каждое ребро \( e ∈ E \) соединяет две вершины, скажем, \( u \) и \( v \). Когда мы считаем степень каждой вершины \( \text{deg}(v) \) (количество ребер, инцидентных вершине \( v \)), каждое ребро \( e = (u, v) \) учитывается ровно дважды: один раз при подсчете степени вершины \( u \) и один раз при подсчете степени вершины \( v \).

Таким образом, если мы просуммируем степени всех вершин:

$$ Σ_{v ∈ V} \text{deg}(v) $$

эта сумма будет равна удвоенному числу всех рёбер в графе, потому что каждое ребро было посчитано дважды.

$$ Σ_{v ∈ V} \text{deg}(v) = 2 \times |E| $$

где \( |E| \) — число рёбер в графе.

Вывод: Сумма степеней всех вершин графа в точности в два раза больше числа рёбер этого графа.