Hamiltonian Paths and Cycles

If a graph is connected and $2e \geq n^{2} - 3n + 6$, then it has a Hamiltonian cycle.

The Dirac--Ore theorem. A graph in which the sum of the degrees of any two non-adjacent vertices is at least $n$ has a Hamiltonian cycle.

Dirac's lemma. If $a_{0} \ldots a_{s}$ is a maximal one among the paths in the graph that pass through each of their vertices only once, $s \geq 3$ and $\deg a_{0} + \deg a_{s} > s$, then this graph has a non-self-intersecting cycle of length $s$.

If a connected graph has a non-self-intersecting cycle of length $s < n$, then this graph has a path of length $s$ passing through each of its vertices only once.

A graph in which the sum of the degrees of any two non-adjacent vertices is at least $n-1$ has a Hamiltonian path.

This graph has at least one non-self-intersecting cycle.

Denote by $v_{1}, \ldots , v_{s}$ a maximal non-self-intersecting cycle in this graph. Denote by $W$ any connected component of the graph obtained from the original graph by deleting the vertices of this non-self-intersecting cycle. Denote by $X$ the set of vertices of the non-self-intersecting cycle that are adjacent to $W$.

Then $\left|X\right| \geq k$.

The vertices $v_{i}, v_{i+1}$ do not both lie in $X$.

If $v_{i}, v_{j} \in X$, then the graph has no edge $v_{i+1} v_{j+1}$.

Is there a Hamiltonian path in the graph in Fig. 8?

Fig. 8. Does this graph have a Hamiltonian path?

Is there a Hamiltonian cycle in the graph in Fig. 9?

Fig. 9. The graph of the Grinberg polyhedron. Does it have a Hamiltonian path?

For which $n$ is there a Hamiltonian cycle in the graph whose vertices are the 3-element subsets of an $n$-element set, two subsets being joined by an edge if they intersect in exactly one element?

Every tournament has a directed Hamiltonian path.

For every $n$ there exists a tournament with $n$ vertices that has at least $n! / 2^{n}$ directed Hamiltonian paths.