Изменения

|proof=

Для графа <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 \cdot \log{n} + 1</tex> уровней. <tex>H</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>.

<br>