I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length.
Here are the conclusions I reached, which I am not sure at all are correct:
If G contains a closed walk of odd length (let's say a u-v walk), then it contains 2 u-v walks, one of even length and another one of odd length so that when added up they give an odd number. Then for every of these u-v walks, we can obtain a u-v path by removing all the repeated fragments of the walk.
We are left now with 2 paths. These two paths might form a cycle or not.
In the case they do form a cycle, we are done (however I know nothing about the length of such cycle).
In the case they do not form a cycle, remove all xy edges s.t. xy belongs to both paths. We will remove an even number of edges before we reach the cycle; but then again, I can't tell the parity of the length).
Thanks a lot!
Best Answer
If you have a closed path $aa$, so the end point is equal to the begin point. If this is the only point that is reached twice you are done.
If there is another point that is reached twice say $v$ then you can make two new closed paths $vv$ were one goes to $a$ and back and the other is the rest. One has to be of odd length. Repeat this argument with the odd length closed walk until you have a cycle.