Revisit of Erdos-Gallai's theorem on the circumference of a graph
Let c, m, n be integers with n >= c >= 3, and let G be a graph of order n with m edges. A classical theorem by Eras and Gallai states that if m > (c - 1)(n - 1)/2, then G contains a cycle of order at least c. In fact, the bound on m in this theorem is not sharp when both n and c are even. In this work we give the sharp value for this case. (C) 2013 Elsevier B.V. All rights reserved.
circumference cycle graph algorithms maximum number of edges