On cycle lengths in graphs of moderate degree
It is shown that for all \(\varepsilon>0\), an integer \(N(\varepsilon)\) exists such that if \(G\) is any graph of order \(n \geq N (\varepsilon)\) with minimum degree \(\delta \geq 32 \sqrt n\), \(G\) contains a cycle of length \(2l\) for each \(l\), \(2 \leq l \leq \delta / (16 + \varepsilon)\). This is a consequence of the following result: If \(l \geq 2\), any bipartite \(G\) of order \(n\) with \(\delta \geq 8l n^{1/l}\) has a cycle of length \(2l\). This last statement holds because otherwise, if we denote by \(V_ i\) the set of vertices of distance \(i\) from an arbitrarily chosen vertex, we have \(| V_ i |/ | V_{i-1} | \geq n^{1/l}\). The inequality yields \(| V |>n\), a contradiction.
scientific article; zbMATH DE number 562646
scientific article