I saw this result in this question:
Any edge that occurs an odd number of times in a closed walk $W$ is part of a cycle in $W$.
From the questions in my introductory graph theory class, this seems like a useful result, and I wanted to prove it as an exercise. It was more difficult than I thought, I'm struggling with defining/using what it means for an edge to occur an odd number of times.
Is this result even true, and if it is, how can it be proved?
Best Answer
Let the walk be $v_1,v_2\ldots,v_t$, where $v_i,v_{i+1}$ are adjacent vertices and $v_t=v_1$. For an edge $uv$ to appear $k$ times means that there exist $k$ distinct indices $j$ such that: $\{v_j,v_{j+1}\}=\{u,v\}$. This edge can appear in the order $uv$ or $vu$.
Do the following: while there exist at least two occurrences of the edge $uv$, do: If the order of some two consecutive appearances of this edge is same: $u,v,P,u,v$ (where $P$ is the part of the walk between consecutive appearances), then replace this segment of the walk ($uvPuv$) with just $uv$; this ensures that the resulting sequence is still a closed walk. Similarly, if the order is $u,v,P,v,u$, replace this with just the vertex $u$. When this process can no longer be repeated, we get a closed walk with the number of occurrences of $uv$ equal to 1.
Now in this reduced closed walk, consider a closed sub-walk $W'$ with smallest number of edges and containing $uv$. We can see that no edge can appear twice in $W'$; If some edge say $xy$ appears at least twice, we can eliminate it. If $xyPxy$ is a subwalk, then consider cases where $P$ contains $uv$ and $P$ does not; in both cases, we can find a shorter closed walk containing $uv$. Similarly if $xyPyx$ is a subwalk.
Thus we get a closed walk containing $uv$ with edges from $W$, and every edge present exactly once, that is a cycle containing $uv$.