Теорема о степени:

Пусть G - связный граф с n вершинами и m ребрами. Тогда сумма степеней всех вершин графа равна удвоенному количеству ребер:
2m = Σdeg(v), где суммирование производится по всем вершинам v из множества вершин графа G.

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

Пусть каждое ребро соединяет вершины v_i и v_j. Тогда степень вершины v_i - это количество ребер, инцидентных этой вершине, т.е. deg(v_i) = deg(v_j) = k. Таким образом, сумма степеней всех вершин графа равна k*n, где n - количество вершин графа.

С другой стороны, количество ребер графа равно m. Так как каждое ребро инцидентно двум вершинам, то каждая вершина участвует в k ребрах, где k - степень каждой вершины. Следовательно, количество ребер равно сумме степеней всех вершин графа: m = Σdeg(v).

Таким образом, получаем уравнение:
m = Σdeg(v) = k*n.

Из двух уравнений:
kn = m,
Σdeg(v) = kn,
следует, что
2m = 2k*n = Σdeg(v).

Таким образом, доказана теорема о степени.