Изменения
→Доказательство необходимости
Предположим, что граф <math>G</math> имеет ориентированный гамильтонов цикл, и покажем, что формула <math>E</math> выполнима. Напомним два важных пункта из предыдущего анализа.
# Если гамильтонов цикл входит в некоторый <math>I_j</math> в узле <math>r_{j}</math>, <math>s_{j}</math> или <math>t_{j}</math>, то он должен выходить из него в узле <math>u_{j}</math>, <math>v_{j}</math> или <math>w_{j}</math> соответственно.
# Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа <math>H</math>, можно характеризовать "экскурсию", совершаемую в некоторое <math>I_j</math>, как переход цикла по дуге, "параллельной" одной из дуг <math>b_{ip} \rightarrow с_c_{i,p+1}</math> или <math>c_{ip} \rightarrow b_{i,p+1}</math>.
Если игнорировать экскурсии в подграфы <math>I_{j}</math>, то гамильтонов цикл должен быть одним из <math>2^n</math> циклов, которые возможны с использованием только подграфов <math>H_i</math> и соответствуют выборам переходов из <math>a_{i}</math> либо в <math>b_{i0}</math>, либо в <math>c_{i0}</math>. Каждый из этих выборов соответствует приписыванию значений переменным из <math>E</math>. Если один из них дает гамильтонов цикл, включающий подграфы <math>I_j</math>, то подстановка, соответствующая этому выбору, должна удовлетворять формуле <math>E</math>.
