Лемма о рукопожатиях — различия между версиями
Kot (обсуждение | вклад) (Новая страница: «== Лемма о рукопожатиях == Сумма степеней всех вершин графа(или мультиграфа без петель) — ч…») |
(Рустам, что со склонением прилагательных?) |
||
| Строка 1: | Строка 1: | ||
== Лемма о рукопожатиях == | == Лемма о рукопожатиях == | ||
| − | Сумма степеней всех вершин графа(или мультиграфа без петель) — четное число, равное удвоенному числу ребер: | + | Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер: |
<math>\Sigma_{v\in V(G)}deg v=2 |E(G)|</math> | <math>\Sigma_{v\in V(G)}deg v=2 |E(G)|</math> | ||
| Строка 10: | Строка 10: | ||
content-style = text-align: justify; | | content-style = text-align: justify; | | ||
content = | content = | ||
| − | Если взять граф с вершинами, вообще не | + | Если взять граф с вершинами, вообще не связанными друг с другом, то сумма степеней этих вершин равна нулю. При добавлении ребра, связывающего любые две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер. |
}} | }} | ||
Версия 01:51, 1 октября 2010
Лемма о рукопожатиях
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер:
Доказательство
Если взять граф с вершинами, вообще не связанными друг с другом, то сумма степеней этих вершин равна нулю. При добавлении ребра, связывающего любые две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.
Следствие 1 В любом графе число вершин нечетной степени четно
Следствие 2 Число ребер в полном графе
