Hamilton Cycles in the path graph of a set of points in convex position

摘要

Let P be a set of n points in convex position in the plane. The path graph G(P) of P is the graph with one vertex for each plane spanning path of P, in which two paths S and T are adjacent if one can be obtained from the other by a single edge exchange. We prove that if n ≥ 3, then G(P) is hamiltonian.