The following problem is Exercise 4.1.5 in Problem-Solving Methods in Combinatorics by Pablo Soberón.
Consider a graph $G$ and $v_1$, $v_2$ two of its vertices. We know that there
are two walks from $v_1$ to $v_2$, one of odd length and one of even length.
Show that in $G$ there is at least one cycle of odd length.
Soution (my trial). We distinguish two cases:
- If the two walks are disjoint, then their union is a cycle of odd lenght (since the sum between an odd and an even number is odd).
- If they are not disjoint, let $v$ a common vertex of the two walks. Then $v$ cuts one of the walks into two smaller walks, say $a=(v_1,v)$ and $b=(v,v_2)$; also $v$ cuts the other walk from $v_1$ to $v_2$ in the problem into two smaller walks, say $a'=(v_1,v)$ and $b'=(v,v_2)$. Now it's easy to see that the union of $a$ and $a'$ is a cycle and the union between $b$ and $b'$ is also a cycle. Supposing both of these cycles have even lenght, we get the contradiction that their union (which is the union of the two walks considered in the hypothesis) is even. So one of the cycles must have odd lenght, which finishes our problem.
Is the following proof correct? Thank you!
Best Answer
Let us recall $2$ theorems from elementary graph theory:
Theorem 1: a graph is bipartite if and only if it contains no odd cycles;
Theorem 2: a graph is bipartite if and only if there exists a vertex colouring with $2$ colours.
Now, for the sake of contradiction, suppose $G$ contains no odd cycles. It then follows from the theorems above that there exists a vertex colouring with $2$ colours.
Let us consider such a colouring, name the colours 'colour $1$' and 'colour $2$'. If $v_1$ is coloured with colour $1$, we can look at the path of odd length, see the vertices must have alternating colours, and conclude that $v_2$ must be coloured with colour $1$.
In a similar way, we can consider the path of even length, see that the vertices must have alternating colours, but conclude that $v_2$ must be coloured with colour $2$, a contradiction.
Edit: I do realise that Theorem 1 stated above is strongly correlated to the question at hand.
So, me and a friend came up with an algorithm to find an odd cycle within this walk of odd length:
Start walking a walk $W$ from $v_1$, starting with the path of even length, and when you have reached $v_2$, walk back using the path of odd length. Do this until, for the first time, you reach a vertex which you have passed before, say $u$. Now, we have a walk that looks like this: $$(u_1=v_1,u_2,\ldots,u_i=u,u_{i+1},\ldots,u_j=v_2,\ldots,u_k=u)$$ for some $i<j<k$. We see that $(u=u_i,\ldots,v_2,\ldots,u_k=u)$ forms a cycle. If this cycle has odd length, we are done. If not, we construct a walk $W_1$ by removing this cycle and walking further along the path of odd length.
We continue doing this until we have either found a cycle of odd length, in which case we are done, or until we reach $v_1$ again. In this case, we have obtained a cycle containing $v_1$. This cycle has odd length since all cycles we have removed from our original walk had even length.