# Path with Bipartite graphs

I have the following problem:
Let $G=(V,E)$ a simple, bipartite graph with the bipartition
${V_1,V_2}$ and let $u,v\in V$ , so that $u\in V_1$ and $v\in V_2$

I'm trying to prove with the use of induction,
that every Path from u to v has an odd (uneven, not divisible by 2) length.

-
Hint: Try instead to prove "any path of even length from $u$ cannot end in $v$". –  Alfonso Fernandez Jan 28 '13 at 16:13
I have to use induction sadly, and I don't see how I could prove such a thing with induction –  Sebastian Hatl Jan 28 '13 at 16:19
You should actually prove the stronger claim "The end point of an even path starting as $u$ must be in $V_1$". Start with the base case, length $0$, which is trivial, then assume it's true for any even path of length $2k$, and prove that when taking two more steps, that is, a path of length $2k+2$, you stay in $V_1$. –  Alfonso Fernandez Jan 28 '13 at 16:49