Non-Isomorphic Smallest Maximally Non-Hamiltonian Graphs

A graph \(G\) is maximally non-hamiltonian \((MNH)\) if \(G\) is not hamiltonian but becomes hamiltonian after adding an arbitrary new edge. Bondy \([2]\) showed that the smallest size \((=\)number of edges) in a \(MNH\) graph of order \(n\) is at least \(\left\lceil\frac{3n}{2}\right\rceil\) for \(n \geq 7\). The fact that equality may hold for infinitely many \(n\) was suggested by Bollobas [1]. This was confirmed by Clark, Entringer, and Shapiro (see [5,6]) and by Xiaobui, Wenzhou, Chengxue, and Yuanscheng [8] who set the values of the size of smallest \(MNH\) graphs for all small remaining orders \(n\). An interesting question of Clark and Entringer [8] is whether for infinitely many \(n\) the smallest \(MNH\) graph of order \(n\) is not unique. A positive answer – the existence of two non-isomorphic smallest \(MNH\) graphs for infinitely many \(n\) follows from results in \([5], [4], [6]\), and \([8]\). But, there still exist infinitely many orders \(n\) for which only one smallest \(MNH\) graph of order \(n\) is known.

We prove that for all \(n \geq 88\) there are at least \(\tau(n) > 3\) smallest \(MNH\) graphs of order \(n\), where \(\lim_{n\to\infty} \tau(n) = \infty\). Thus, there are only finitely many orders \(n\) for which the smallest \(MNH\) graph is unique.