Hi I am new in graph theory and I would sincerely appreciate your help with my proof. This is not for a homework, I am just practicing for one of my courses.
So, my approach to prove this statement was by induction on the length of the closed walks. I already have the base case. Now, assume that the statement is true for any closed walk $(v_1, v_2, …, v_k)$ where k < n and k is odd. Assume we have a closed walk $A = (v_1, …, v_n = v_1)$ where n is odd. So if we do not have any repeated vertices other than $v_1$ and $v_n$ then we are done and $A$ is an odd cycle. If not, then we have some $v_i$ such that $A$ can be seen as $(v_1, …, a, v_i, …, v_i, b,…, v_n = v_1)$. So we have one closed walk $ W = (v_i, …, v_i)$ that has length $<n$ and we can apply induction hypothesis on that walk. This is the point where I do not know how to prove. I would like to say that the sequence $V = (v_1, …., a, b, …., v_n = v_1)$ is a closed walk. But how do I even know that it is a walk ? Also how do I know that it is disjoint from the other walk? I have seen that this technique is applied in some proofs of graph theory but I am not sure why V would be a closed walk.
Again any help would be greatly appreciated and, as I said, this is not a problem from an assignment.
Best Answer
Suppose that $i<j$, and $v_i=v_j$. Then $v_iv_{i+1}\ldots v_{j-1}v_j$ is a closed walk, and $v_jv_{j+1}\ldots v_{n-1}v_1\ldots v_i$ is also a closed walk. If $\ell_1$ is the length of the first walk and $\ell_2$ the length of the second walk, then $\ell_1+\ell_2=n$, and since $n$ is odd, one of $\ell_1$ and $\ell_2$ must be odd and the other even. Pick the one of odd length, and apply your induction hypothesis.
If I understand your argument correctly, you want to cut out $v_{i+1}\ldots v_j$ and use the path $v_1\ldots v_iv_{j+1}\ldots v_n$. That’s my second path, just listed from a different starting point, and there’s no guarantee that its length is odd: $\ell_2$ might be even, in which case it’s the other path, the one through the deleted part, that you want to use.