On Smallest Maximally Nonhamiltonian Graphs

Bollobas posed the problem of finding the least number of edges, \(f(n)\), in a maximally nonhamiltonian graph of order \(n\). Clark, Entringer and Shapiro showed \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 36\) and all odd \(n \geq 53\). In this paper, we give the values of \(f(n)\) for all \(n \geq 3\) and show \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 20\) and odd \(n \geq 17\).