64
правки
Изменения
→Транзитивность
'''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути. Рассмотрим граф <tex>T - s</tex>, в нем существует единственный гамильтонов путь (по предположению), значит и в <tex>T</tex> он будет единственным.
<tex>5 \Rightarrow 1: </tex> Пусть <tex>P=\{v_1, v_2, \ldots, v_n\}</tex> — единственный гамильтонов путь. Пусть найдется <tex>m</tex> — наименьший индекс такой, что в вершину <tex>v_m</tex> идет ребро из вершины с большим индексом, а <tex>v_k</tex> — вершина с наибольшим индексом, из которой ребро ведет в <tex>v_m</tex>. Возможно несколько случаев:# <tex> m \neq 1, k \neq n: </tex> Из <tex>v_{m -1}</tex> ведет ребро в <tex>v_{m+1}</tex> (по минимальности <tex>m</tex>), а из <tex>v_m</tex> ведет ребро в <tex>v_{k +1}</tex> (по максимальности <tex>k</tex>). Тогда будет существовать еще один гамильтонов путь <tex>P_1 = \{v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{k}, v_m, v_{k+1}, \ldots, v_n\}</tex>.# <tex> m \neq 1, k = n: </tex> <tex>P_1 = \{v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{n}, v_m\}</tex>.# <tex> m = 1, k \neq n:</tex> <tex>P_1 = \{v_2, \ldots, v_{k}, v_1, v_{k+1}\}</tex>#<tex> m = 1, k = n:</tex> <tex>P_1 = \{v_2, \ldots, v_n, v_1\}</tex>
'''Замечание''' Может достигаться равенство <tex>m + 1 = n</tex>, в этом случае нужно исключить из пути <tex>2</tex> последовательных вхождения <tex>v_n</tex>.
Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого <tex>m</tex>, т.е <tex>(v_i, v_j) \in E \Leftrightarrow i < j</tex>. Значит <tex>\forall i, j, k: 1 \leqslant i, j, k \leqslant n, (v_i, v_j) \in E \land (v_j, v_k) \in E \Rightarrow i < j \land j < k \Rightarrow (v_i, v_k) \in E </tex>.
