# A closed walk in a graph which has a subgraph consisting of edges used odd number of times

Let W be a closed walk in a graph G. Let H be the subgraph of G consisting of edges used an odd number of times in W. Prove that $d_H(v)$ is even for every $v\in V(G)$.

I have proved the result if W is a closed trail. I have also shown that any such edge will also be part of a cycle in W (not sure whether that helps though).

-
Since the walk is closed, the number of edges in the walk that are incident in $v$, counting multiplicity, is even, since every time you go in, you also have to go out. The edges that are used an even number of times contribute an even number of "entries and exits" into $v$. What about the edges that are used an odd number of times? –  Arturo Magidin May 8 '11 at 5:29
I think I have the idea, just cant seem to express it properly. An edge that is used an odd number of times will enter and exit into v, an odd number of times. As total entries & exits is even and the even used edges imply even entries and exits, so the total entries and exits for odd used edges would be even. Since each of them individually contribute odd so they must be even in number. Is this explanation correct? –  Shahab May 8 '11 at 6:18
Essentially. I can suggest some notation that might make things easier, but the point is the there must be an even number of "oddly used" edges incident in $v$ for the totals to work out. –  Arturo Magidin May 8 '11 at 18:03

Let $v$ be a vertex in $G$, and let $e_1,\ldots,e_n$ be all the edges of $G$ that are incident in $v$. Let $m_i$ be the number of times that $e_i$ is used in the walk $W$ (counting multiplicity).
Because the walk is closed, the number of edges in $W$ (counting multiplicity) that are incident in $v$ is even. That means that $$m_1+\cdots+m_n \equiv 0 \pmod{2}.$$
Reordering the edges if necessary, assume that $m_1,\ldots,m_k$ are odd, $0\leq k\leq n$, and $m_{k+1},\ldots,m_n$ are even. That means that of all $n$ edges incident in $v$, only $e_1,\ldots,e_k$ lie in $H$. You need to show that $k$ is even. Now note that $m_i\equiv 1\pmod{2}$ if $1\leq i\leq k$, and $m_i\equiv 0\pmod{2}$ if $k\lt i\leq n$.