Hamiltonian Paths in Non-Hamiltonian Graphs

Erik Carlson, Willem Fletcher, MurphyKate Montee

Published 2021-06-25Version 1

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<n<9$, if $G$ admits Hamiltonian paths starting at every vertex then $G$ is Hamiltonian. We also show that this is not true for $n>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.