### Edge condition for long cycles in bipartite graphs

*Lech Adamus*

#### Abstract

The following problem was solved by Woodall in 1972: for any pair of
nonnegative integers n
and k<n / 2-1
find
the minimum integer g(n,k) such that every graph with
n
vertices and at least g(n,k) edges contains a cycle of
length
n-k. Woodall proved even more: the size
g(n,k),
in fact, guarantees the existence of cycles C

_{p}for all 3≤p ≤n-k. In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n, m≤n, and size greater than n(m-k-1)+k+1 contains a cycle of length 2m-2k, where m≥1 / 2k^{2}+ 3 / 2k + 4, k∈N. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m-2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m≥2k+2.Full Text: PDF PostScript