Degree conditions for hamiltonicity: Counting the number of missing edges

In 1960 Ore proved the following theorem: Let G be a graph of order n  . If d(u)+d(v)⩾nd(u)+d(v)⩾n for every pair of nonadjacent vertices u   and vv, then G is hamiltonian. In this note we strengthen Ore's theorem as follows: we determine the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. Some other sufficient conditions (i.e. Fan's condition) for hamiltonian graphs are strengthened as well.