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