Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
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
up vote 1 down vote accepted

Okay, so the idea is there, but writing it out is causing trouble. When that happens, it's usually a good idea to write down things carefully.

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.