748
правок
Изменения
→Ориентированный граф
|statement=
Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное число, равное удвоенному числу ребер:
<br /> <tex>\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2 \cdot|E(G)| </tex>
|proof=
[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot|E|</tex>]]
Аналогично доказательству леммы о рукопожатиях неориентированном графе.
То есть возьмем пустой граф и будем добавлять в него ребра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа четна и равна удвоенному числу ребер.
}}
==== Бесконечный граф ====
[[Файл:inf_grap.png|thumb|300px|right|Пример бесконечного графа, в котором не выполняется лемма]]
