Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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

 
discard

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

Browse other questions tagged or ask your own question.