bipartite graph cycles

Question

I hope anybody can help me. I am considering the following problem: For every $d$ in $\mathbb{N}_{ \geq 2}$ determine the largest value $f(d)$ such that every bipartite graph G of minimum degree $\delta(G)=d$ contains a cycle of length at least f(d). My assumption is that $f(d)=2d$ but I'm not sure how to prove this. Can anybody give me a hint?

Answer 1

Start with a vertex in the graph, say $a_1$. Pick one of its neighbors in the other set. Let's call it $b_1$. Now move to one of its neighbors that is not $a_1$, and call it $a_2$. We can continue this traversal and keep visiting new vertices, since minimum degree is $d$, until we hit $b_d$. At this point, we have traversed $2d$ vertices in this order $a_1b_1a_2b_2\dots a_db_d$. Now if $b_d$ is a neighbor of $a_1$, we have a cycle of length $2d$. If not, again using the fact that minimum degree is $d$, $b_d$ has a neighbor that is not one of $a_2, \dots, a_d$. Call it $a_{d+1}$ and add it to the sequence. Now if this vertex is the neighbor of $b_1$, we are done. Otherwise, we add another vertex to our sequence. At any point in the sequence, if $a_k$ (or $b_k$, $k> d$) has a neighbor in one of $b_1,\dots,b_{k-d+1}$ (or $a_1,\dots,b_{k-d}$), we are done. If not, we know we can always find another vertex to add in this sequence. If there are no more new vertices left in the graph, then $a_k$ (or $b_k$) must have a neighbor in one of $b_1,\dots,b_{k-d+1}$ (or $a_1,\dots,b_{k-d}$), again giving a cycle of length at least $2d$.

The above proves that you can find a cycle of length at least $2d$. Its easy to find a counter example where there is no cycle of length $2d+1$, which proves that $f(d)=2d$.