Cycles in 2-connected graphs (Q705891): Difference between revisions

\textit{P. Erdös} and \textit{T. Gallai} [Acta Math. Acad. Sci. Hung. 10, 337--356 (1959; Zbl 0090.39401)] showed that for any integer \(c\geq 2,\) if \(G\) is a graph on \(n\) vertices with more than \(c(n-1)/2\) edges, then \(G\) contains a cycle of length more than \(c\). Woodall conjectured that if \(2\leq c\leq n-1,\) and \(G\) is a 2-connected graph on \(n\) vertices with more than \(\max \{f(n,2,c),f(n,\left\lfloor c/2\right\rfloor ,c)\}\) edges, then \(G\) contains a cycle of length more than \(c,\) where \(f(n,t,c)=\binom{c+1-t}{2}+t(n-c-1+t).\) In the paper the above conjecture of Woodall is confirmed.