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

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

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

Каждое ребро \( e ∈ E \) соединяет две вершины, скажем \( v_i \) и \( v_j \). При подсчёте суммы степеней всех вершин, каждое ребро \( e \) учитывается ровно дважды: один раз при подсчёте степени вершины \( v_i \) (так как одно из рёбер, выходящих из \( v_i \), является \( e \)) и один раз при подсчёте степени вершины \( v_j \) (так как одно из рёбер, выходящих из \( v_j \), также является \( e \)).

Таким образом, если \( d(v) \) обозначает степень вершины \( v \), то сумма степеней всех вершин \( ∑_{v ∈ V} d(v) \) равна удвоенному количеству рёбер, то есть \( 2|E| \).

Следовательно, \( ∑_{v ∈ V} d(v) = 2|E| \).

Доказано.