577
правок
Изменения
→Теорема Гуйя-Ури
|proof=
Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят как минимум два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить). <br>
Пусть <tex>A</tex> {{---}} множество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>, а <tex>a</tex> {{---}} их количество. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>A</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней <tex>l + 1</tex> вершина в цикле <tex>C</tex> не является ни прямым предком отцом <tex>v_0</tex>, ни прямым потомком сыном <tex>v_l</tex>. <br>Рассмотрим оставшуюся <tex>a - 1</tex> вершину множества <tex>A</tex>, отличную от <tex>y</tex>. В следующую за каждой из них, очевидно, не может приходить ребро из <tex>v_l</tex>. Следовательно, как минимум <tex>(a - 1) + (l + 1) = a + l</tex> вершин <tex>C</tex> не являются прямыми потомками сыновьями <tex>v_l</tex>, в противном случае, опять же, граф содержал бы цикл длины <tex>> k</tex>. <br>Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит теорема доказана.
}}
