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