748
правок
Изменения
→Неориентированный граф
|statement=
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер:
<br /> <tex> \sum\limits_{v\in V(G)} deg\ v=2 \cdot|E(G)|</tex>
|proof=
Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.
}}
Например, для следующего графа выполнено: <tex>deg(1)+...+deg(6)=16=2\cdot|E|</tex>
[[Файл:undir_grap.png]]
'''Следствие 1.''' В любом графе число вершин нечетной степени четно.
'''Следствие 2.''' Число ребер в полном графе <tex>\frac{n\cdot(n-1)}{2} </tex>.
<br />
