Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.