пути обхода вершин i1 ,i2 ,i3 ,..., ia-1,ia. Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i1, i2, i3,..., ia для любого а, имеющего значения в пределах от 4-х до п.
Значения а не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины последовательно в одном из двух возможных вариантов обхода: i1, i2, i3, i4 или i1, i3, i2, i4.
Пусть оптимальный гамильтонов цикл обходит вершины графа в последовательности
i1,i2,i3,..., in,i1. (9.2.1.a)
Гамильтонов цикл, оптимальный для определенного значения а, назовем а-оптимальным. Для а = 4 справедливо неравенство:
Условие (9.2.2) необходимо проверить для всех ik = i1 , i2,..., in и, если оно для всех 4 справедливо, то это необходимое и достаточное условие того, что гамильтонов цикл 4-оптимален. Просуммировав левые и правые части неравенств, получающихся при значениях ik = i1,i2,..., in, получаем необходимое условие 4-оптимальности в виде: 
Справедливо следующее условие: Если гамильтонов цикл a1-оптимален, то он а2- оптимален для любого a2<a1.
Если это условие не выполняется, т.е. a1-оптимальный гамильтонов цикл не является a2-оптимальным, то какой-то из простых путей длины a1 можно улучшить изменением обхода каких-то а2 вершин, что противоречит условия a1-оптимальности.
Перейдем к определению условия а-оптимальности, получаемого аналогично тому, как условие (9.2.3) получено из (9.2.2), из системы неравенств вида (9.2.2,), для любого a=const суммированием для всех ik=1,2, ... , п
Для каждого значения k будет иметь место система из ((а-2)!-1) неравенств по числу элементов множества Р, состоящего из (а-2)! перестановок чисел i'k+1, i'k+2, ..., i'k+a-2 При этом мы полагаем, что
Обозначим левую и правую части условия (9.2.4) буквами А и В, соответственно: А ? В.
В левой части неравенства вес каждого ребра, принадлежащего проверяемому участку гамильтонова цикла, участвует точно по одному разу в каждом неравенстве системы из ((а-2)!- 1) неравенств, задаваемых перестановками, принадлежащими множеству Р, при фиксированной начальной вершине. Кроме этого, при заданном a=const, если производить проверку выполнения условия (9.2.4), изменяя последовательно номер начальной вершины от i1 до in, то любое ребро гамильтонова цикла появится точно в (а-1) системах из этих ((а-2)!-1) неравенств как первое по счету, второе, третье и т.д. (а-1)-е ребро в проверяемых участках гамильтонова цикла.
Следовательно, левая часть неравенства (9.2.4) имеет вид:
Выражение для правой части условия (9.2.4) можно записать в виде: 
Для того, чтобы получить выражение для правой части условия (9.1.4), необходимо найти число появлений ребер графа вида (ic, ic+N ) в каждой системе из ((а-1) !-1) неравенств, задаваемых определенным значением k, а также во всех 
