Degree conditions for Hamiltonicity: counting the number of missing edges (Q868355)

Dirac showed that if \(G\) is a graph of order \(n\) having minimum degree at least \(n/2\), then \(G\) is Hamiltonian. Ore strengthened this result by showing that if the sum of the degrees of every pair of non-adjacent vertices is at least \(n\), then \(G\) is Hamiltonian. Fan showed that if \(G\) is a 2-connected graphs of order \(n\) such that \(\max\{d(u), d(v)\} \geq n/2\) for every pair \(u,v\) of vertices distance \(2\) apart, then \(G\) is Hamiltonian. The authors strengthen each of these results by showing that if the conditions are not violated too often, then \(G\) is still guaranteed to be Hamiltonian. In particular they show that if \(G\) is a graph of order \(n\) and minimum degree \(\delta < n/2\) having at most \(\delta -1\) vertices of degree less than \(n/2\), then \(G\) is Hamiltonian. Similar improvements for Ore and Fan's results are given. They also show that their results are best possible.