Изменения

== Лемма о рукопожатиях Неориентированный граф == 

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

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

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

''Следствие 2''== Источники информации ==Число ребер в полном графе <math>\frac{n(n* Lecture Notes on Graph Theory By Tero Harju, Department of Mathematics University of Turku, 2011 — с. 7-1)}{2} <8* [http://en.wikipedia.org/wiki/math>Handshaking_lemma Handshaking lemma — Wikipedia][[Категория: Алгоритмы и структуры данных]][[Категория: Основные определения теории графов]]