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