577
правок
Изменения
→Лемма о длине цикла в ориентированном графе
{{Лемма
|about=о длине цикла в ориентированном графе
|statement= Пусть <tex>G</tex> {{---}} произвольный [[Основные определения теории графов#def_undirected_graph_1|ориентированный граф]] и для каждой вершины <tex>v \in V(G)</tex> выполняется <tex>deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.
|proof=
Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Из последней вершины <tex>v_s</tex> выходит хотя бы <tex>\delta - 1</tex> ребро в вершины, отличные от <tex>v_{s - 1}</tex>. Так как путь <tex>P</tex> максимальный, то продлить его нельзя, а значит, что из <tex>v_s</tex> выходят ребра только в вершины, содержащиеся в пути <tex>P</tex>. Пусть <tex>v_m \in P</tex> {{---}} вершина с наименьшим номером, в которую входит ребро из <tex>v_s</tex>. Тогда во множество <tex>\{v_m \dots v_{s - 1}\}</tex> входят не менее <tex>\delta</tex> ребер, выходящих из <tex>v_s</tex>. То есть в это множестве хотя бы <tex>\delta</tex> вершин. Значит, в цикле <tex>v_m \dots v_{s - 1} v_s</tex> не менее <tex>\delta + 1</tex> вершины.
