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

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

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

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

Степень вершины \( v \) (обозначается \( \text{deg}(v) \)) — это количество рёбер, инцидентных этой вершине.

Сумма степеней всех вершин графа равна:

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

Каждое ребро \( e \) в графе соединяет две вершины, скажем \( u \) и \( v \). При подсчёте суммы степеней вершин, каждое ребро \( e = (u, v) \) учитывается ровно дважды: один раз при подсчёте степени вершины \( u \) и один раз при подсчёте степени вершины \( v \).

Таким образом, сумма степеней всех вершин графа в точности равна удвоенному числу рёбер в графе.

Математически это выражается формулой:

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

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

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

Доказано.