Fleischner's theorem states that the square of a two-connected graph has one of these, and Chvatal conjectured in 1973 that e
Fleischner's theorem states that the square of a two-connected graph has one of these, and Chvatal conjectured in 1973 that every t-tough graph has one of these for some integer t. Every graph with more than three vertices and a degree greater than half the number of vertices has one of these, a result known as Dirac's theorem. The task of finding these is incomplete for both directed and undirected graphs, and finding one of these for a graph with the minimum edge cost is the Traveling Salesman Problem. For 10 points, name this tour through a graph which starts and ends at the same vertex and contains every other vertex exactly once.
Fleischner's theorem states that the square of a two-connected graph has one of these, and Chvatal conjectured in 1973 that every t-tough graph has one of these for some integer
Hamiltonian cycle [prompt on Hamiltonian; do not accept "Hamiltonian path"]