Extensions of a theorem of Erdős on nonhamiltonian graphs

Let n , d be integers with 1 ≤ d ≤ ⌊ n − 1 2 ⌋ , and set h ( n , d ) : =n − d 2 + d 2 . Erdős proved that when n ≥ 6 d , each n ‐vertex nonhamiltonian graph G with minimum degree δ ( G ) ≥ d has at most h ( n , d ) edges. He also provides a sharpness example H n , dfor all such pairs n , d . Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graph G on n vertices with δ ( G ) ≥ d and more than h ( n , d + 1 ) edges is a subgraph of H n , d . In this article, we show that not only does the graph H n , dmaximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at least d , but in fact it maximizes the number of copies of any fixed graph F when n is sufficiently large in comparison with d and | F | . We also show a stronger stability theorem, that is, we classify all nonhamiltonian n ‐vertex graphs with δ ( G ) ≥ d and more than h ( n , d + 2 ) edges. We show this by proving a more general theorem: we describe all such graphs with more thann − ( d + 2 ) k + ( d + 2 )d + 2 k − 1copies of K k for any k .