Please check this graph theory solution I was thinking of 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!
 A: Wlog we can assume if some edge is on both path, we can ignore it (i.e. contract it vertices into a single vertex). Let $d$ be total of deleted edges.
Let these walks intersect at $u_0=v_1,u_1,u_2,...,u_k=v_2$. Then these vertices make a partitions $a_1,...,a_k$ of a first walk and $b_1,...,b_k$ of a second walk.

Let $l(a_i)$ be a lenght of walk $a_i$. Now we have $$l(a_1)+l(a_2)...+l(a_k) = odd-d$$ and $$l(b_1)+l(b_2)...+l(b_k) = even-d$$
so their sum $$\underbrace{\Big(l(a_1)+l(b_1)\Big)}_{d_1} +\underbrace{\Big(l(a_2)+l(b_2)\Big)}_{d_2}...+ \underbrace{\Big(l(a_k)+l(b_k)\Big)}_{d_k}= odd$$
So one of $d_1,d_2,...d_k$ must be odd and we are done.
A: 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.
A: The best way to proceed is a modification of your first argument.
Whether or not two walks are disjoint, their union is a closed walk of odd length. So there exists at least one odd closed walk in the graph.
Let $W$ be the shortest closed walk of odd length in the graph. There are two cases:

*

*$W$ is a cycle, and we're done.

*$W$ visits some vertex $v$ more than once. Then, starting at $v$, break $W$ up into segments $W_1, \dots, W_k$ that start and return to $v$, without visiting $v$ in between. These are all closed walks shorter than $W$, so they must all have even length. But then, the length of $W$ is the sum of $k$ even lengths, so it is also even, contradiction.

