Изменения

Для графа <tex>G</tex> с <tex>n </tex> вершинами построим граф <tex>G'</tex> такой, что в <tex>G</tex> есть Гамильтонов цикл тогда и только тогда, когда в <tex>G'</tex> есть <tex>n^{n^2}</tex> циклов. Чтобы получить <tex>G'</tex>, заменим каждое ребро <tex>(u,v)</tex> из <tex>G</tex> на блок <tex>H</tex>. Блок состоит из <tex>m = n * \log{n} + 1</tex> уровней. <tex>G</tex> представляет из себя ацикличный граф, а значит циклы в <tex>G'</tex> соответствуют циклам в <tex>G</tex>. Кроме того, существует <tex>2^m</tex> различных путей между <tex>u</tex> и <tex>v</tex> внутри блока, следовательно простому циклу длины <tex>l</tex> в <tex>G</tex> соответствует цикл длины <tex>2^{(ml)}</tex> в <tex>G'</tex>.

Заметим, что , если граф <tex>G</tex> содержит гамильтонов цикл, то в <tex>G'</tex> существует минимум <tex>2^{m(n-1)mn} > n^{n^2}</tex> циклов.

Проверим в обратную сторону. Если в <tex>G</tex> не существует Гамильтонова цикла, то самый длинный цикл в <tex>G</tex> имеет длину не больше <tex>n-1</tex> и число циклов не может превысить <tex>n^{n-1}</tex>. Таким образом, в <tex>G'</tex> будет не более чем <tex>(2^m)^{n-1} * n^{n-1} < n^{n^2}</tex> циклов.му входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер.