Lower bound for the size of maximal nontraceable graphs (Q2571275)

A graph \(G\) is maximal nontraceable, if it does not contain a Hamiltonian path, but each graph obtained by adding an edge to \(G\) has a Hamiltonian path. This paper investigates the maximum number of edges that a maximal nontraceable graph can have. This maximum for a graph with \(n\) edges is \(\lceil (3n-2)/2 \rceil\) if \(n\geq 54\), as well as for some values between 12 and 51. For all \(n\leq 9\), exact bounds are also given. For a few values between 11 and 53, the problem is still open.