333
правки
Изменения
Нет описания правки
Аналогично доказательству леммы о рукопожатиях неориентированном графе.
}}
==== Бесконечный граф ====
[[Файл:inf_grap.png|thumb|325px300px|right|Пример бесконечного графа, в котором не выполняется лемма]]
В бесконечном графе лемма не работает, даже в случае с конечным числом вершин нечетной степени. Покажем это на примере.
При выборе бесконечного пути из вершины <tex> V </tex> (см. рисунок справа) имеем путь, в котором все вершины кроме стартовой имеют четную степень, что противоречит следствию из леммы.
==== Регулярный граф ====
В графе с <tex> n </tex> вершинами, степени которых равны <tex> k</tex> (регулярный граф), ровно <tex>\frac{kn}{2} </tex> ребер.
''Следствие'' Если степень каждой вершины нечетна и равна <tex> k</tex>, то количество ребер кратно <tex> k </tex>.
== Источники ==
