Degree sums for edges and cycle lengths in graphs

Let G be a graph of order n, satisfying d(u) + d(v) greater than or equal to n,for every edge uv of G. We show that the circumference - the length of a longest cycle - of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = K-r,K-r with r = n/2. (C) 1997 John Wiley & Sons, Inc.