Изменения

Сумма степеней всех вершин графа (или мультиграфа без петель) — четное чётное число, равное удвоенному числу реберрёбер:<br /> <tex> \sum\limits_{v\in V(G)} deg\ v=2 \cdot|E(G)|</tex> 

Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна чётна и равна удвоенному числу реберрёбер.

<br />[[Файл:undir_grap.png]] '''Следствие 1.''' В любом графе число вершин нечётной степени чётно.

'''Следствие 12.'''В любом Число рёбер в полном графе число вершин нечетной степени четно<tex dpi=150>\frac{n\cdot(n-1)}{2} </tex>.

''Следствие 2''Число ребер в полном графе <tex>\frac{n(n-1)}{2} <br /tex>

==== Ориентированный граф ====

Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное чётное число, равное удвоенному числу реберрёбер:<br /> <tex>\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2 \cdot |E(G)| </tex>

[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot |E|</tex>]]Аналогично доказательству леммы о рукопожатиях неориентированном графе. То есть возьмем пустой граф и будем добавлять в него рёбра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер.

==== Регулярный Бесконечный граф ====В графе с <tex> n </tex> вершинами, степени которых равны <tex> k</tex> (регулярный граф)[[Файл:inf_grap.png|thumb|300px|right|Пример бесконечного графа, ровно <tex>\frac{kn}{2} </tex> ребер.в котором не выполняется лемма]]

''Следствие'' Если степень каждой вершины нечетна и равна <tex> k</tex>В бесконечном графе лемма не работает, то количество ребер кратно <tex> k </tex>даже в случае с конечным числом вершин нечётной степени. Покажем это на примере.

==== Бесконечный граф ====[[Файл:inf_grapПри выборе бесконечного пути из вершины <tex> V </tex> (см.png|thumb|325px|right|Пример бесконечного графарисунок справа) имеем путь, в котором не выполняется лемма]]все вершины кроме стартовой имеют чётную степень, что противоречит следствию из леммы.

== Регулярный граф =={{Определение|definition=Граф называется '''регулярным''', если степени всех его вершин равны.}}{{Утверждение|statement=В бесконечном регулярном графе лемма не работает, даже в случае с конечным числом вершин нечетной степени. Покажем это на примере<tex> n </tex> вершинами ровно <tex dpi=150>\frac{k\cdot n}{2} </tex> рёбер.

При выборе бесконечного пути из }}   {{Утверждение|statement=Если степень каждой вершины нечётна и равна <tex> V k</tex> , то количество рёбер кратно <tex> k </tex>.|proof= [[Файл:reg_grap.png|thumb|300px|right|Регулярный граф с <tex dpi=140>\frac{k\cdot n}{2} = \frac{3\cdot 6}{2}=9 </tex> рёбрами ]]Действительно, так как степень каждой вершины нечётна, то число вершин в графе чётно(смтак сумма степеней всех вершин чётна). рисунок справа) имеем путьПусть <tex> n = 2\cdot r </tex>, в котором все вершины кроме стартовой имеют четную степеньто равенство принимает вид <tex dpi=150>|E| =\frac{k\cdot n}{2} = \frac{2\cdot k\cdot r}{2}=k\cdot r </tex>, что противоречит следствию из леммыто есть количество рёбер кратно <tex> k</tex>.}}

== Источники информации ==