Almost all Graphs have a Spanning Cycle
John W. Moon · Canadian Mathematical Bulletin · 1972
A graph is a collection of nodes some pairs of which are joined by a single edge. A k-path , or a path of length k , is a sequence of nodes {p 1 p 2 ,… P k+1 } such that P i is joined to p i+1 for 1 ≤i≤ k ; we assume the nodes are distinct except that p 1 and p k+1 may be the same in which case we call the path a k-cycle or a cycle of length k . (Notice that two nodes joined by an edge determine a 2-cycle according to this definition; it will also be convenient to regard a single node as a 1-cycle.) A spanning path or cycle is one that involves every node of the graph. One of the unsolved problems of graph theory is to characterize those graphs that have a spanning path or cycle.