Cycles · Hamiltonian Graphs

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

A Hamiltonian path (cycle) is a path (cycle) that visits each vertex of the graph exactly once.

Above, we saw easily verifiable criteria for Eulerian graphs: it is easy to determine whether a graph has an Eulerian cycle and to find it. One cannot expect a similarly simple criterion for Hamiltonicity: the problem of checking Hamiltonicity is NP-hard. Moreover, we still do not know algorithms that work faster than \(2^{n}\).

Below, we present several sufficient conditions for the existence of a Hamiltonian path.

For the curious 🤓

Gray code demonstrates that a Hamiltonian cycle exists in the Boolean cube—an undirected graph \(G(V,E)\), where \(V=\{0,1\}^{n}\) and \(\{u,v\} \in E\) if the strings \(u,v\) differ in exactly one bit. Relatively recently, it was also proven that a Hamiltonian cycle exists in the middle level of the cube—on edges between weight levels \(n/2-1\) and \(n/2\). The corresponding hypothesis is called the middle levels conjecture and remained open for over thirty years.