= Solution
Let $P=v_0\ldots v_\ell$ be a longest path. All neighbours of $v_0$ lie on $P$, in the colour class opposite to $v_0$, so $\ell\geq2k-1$. If $\ell\geq2k$, the first $2k$ edges give the required path. Otherwise $\ell=2k-1$, and all $k$ vertices of the opposite colour on $P$ must be neighbours of $v_0$; in particular $v_0v_\ell$ is an edge, giving a cycle of length $2k$. The graph $K_{k,k}$ has minimum degree $k$ but only $2k$ vertices, so it has no path of length $2k$.
For the stronger assertion, assume there is no $4$-cycle. Rotate a longest path about each edge from $v_0$ to obtain $k$ possible endpoints in the colour class of $v_0$. Every neighbour of each rotated endpoint lies on $P$, since otherwise the corresponding path could be extended. In a $4$-cycle-free bipartite graph, two vertices in one colour class have at most one common neighbour. The <neighbourhood bound for a square-free bipartite graph> therefore shows that the colour class opposite to $v_0$ contains at least $2k-1$ vertices of $P$. If the endpoints have opposite colours, repeating the argument from $v_\ell$ gives the same bound for the other class. If they have the same colour, their class has one more vertex on $P$ than the opposite class. In either case $P$ has at least $4k-2$ vertices and length at least $4k-3$. Consequently $G$ contains either such a path or a $4$-cycle.
Back to article page
