Лемма о рукопожатиях — различия между версиями
(Значок суммы..) |
Kot (обсуждение | вклад) м (→Лемма о рукопожатиях: , привел доказательство к нормальному виду) |
||
| Строка 1: | Строка 1: | ||
== Лемма о рукопожатиях == | == Лемма о рукопожатиях == | ||
| − | + | {{Лемма | |
| + | |statement= | ||
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер: | Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер: | ||
| + | <br> | ||
<math>\sum\limits_{v\in V(G)} deg\ v=2 |E(G)|</math> | <math>\sum\limits_{v\in V(G)} deg\ v=2 |E(G)|</math> | ||
| − | + | |proof= | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Если взять граф с вершинами, вообще не связанными друг с другом, то сумма степеней этих вершин равна нулю. При добавлении ребра, связывающего любые две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер. | Если взять граф с вершинами, вообще не связанными друг с другом, то сумма степеней этих вершин равна нулю. При добавлении ребра, связывающего любые две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер. | ||
}} | }} | ||
| + | |||
| + | <br> | ||
''Следствие 1'' | ''Следствие 1'' | ||
Версия 05:43, 6 октября 2010
Лемма о рукопожатиях
| Лемма: |
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер:
|
| Доказательство: |
| Если взять граф с вершинами, вообще не связанными друг с другом, то сумма степеней этих вершин равна нулю. При добавлении ребра, связывающего любые две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер. |
Следствие 1 В любом графе число вершин нечетной степени четно
Следствие 2 Число ребер в полном графе
