Hamiltonian Paths in Non-Hamiltonian Graphs

A graph $G$ with $n$ vertices is \emph{Hamiltonian} if it admits an embedded cycle containing all vertices of $G$. In any Hamiltonian graph, each vertex is the starting point of a Hamiltonian path. In this paper we explore the converse. We show that for $2 9$. We then investigate the number of \emph{pairs} of vertices in a non-Hamiltonian graph $G$ which can be connected by Hamiltonian paths. In particular we construct a family of non-Hamiltonian graphs with approximately 4/5 of the pairs of vertices connected by Hamiltonian paths.