Non-isomorphic smallest maximally non-Hamiltonian graphs (Q2715965)

A graph \(G\) is maximally non-Hamiltonian (MNH) if \(G\) is not Hamiltonian but adding to \(G\) any edge results in a Hamiltonian graph. The main result presents a construction based on a modification of Isaacs' snarks, showing that, for any \(n\geq 88\), there are at least \(\tau (n)\) smallest (i.e. with minimum number of edges) MNH graphs of order \(n\), where \(\tau (n)\geq 3\) and \(\lim _{n\to \infty} \tau (n)=\infty \). Thus, only a finite number of orders \(n\) remain for which only a unique smallest MNH graph is known.