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 {p1 p2,… Pk+1} such that Pi is joined to pi+1 for 1 ≤i≤k; we assume the nodes are distinct except that p1 and pk+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.