Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Hello, I'm new to combinatorics so I'm having a bit of trouble. The question I'm having trouble with goes like this:

Let $W=v_0e_1v_1\ldots e_nv_n$ be a walk in a graph $G$, such that $v_0 =v_n$ and all the edges $e_1,\dotsc,e_n$ are distinct. Prove that there exists a set ${C_1,\dotsc,C_m}$ of cycles in $G$ such that ${e_1,\dotsc,e_n}=E(C_1)\cup\ldots\cup E(C_m)$, and $E(C_s)\cap E(C_r) =\emptyset$ for all $s\ne r$.

Any help would be great!

share|cite|improve this question
Some tips on formatting: a) If you write dots using ... instead of \ldots or \dotsc or the like, they don't get the proper spacing. b) If you put words like "and" inside the dollar signs, they're interpreted as a juxtaposition of variable names and get corresponding italics and spacing. c) If you put things like = outside the dollar signs, they get the wrong font and spacing. d) You can use \ne instead of \not=. – joriki Nov 1 '12 at 22:09
up vote 1 down vote accepted

Start from $v_0$ and follow the edges, appending them to an edge sequence, until you hit some vertex again that you'd already encountered. The edges between those two encounters form a cycle $C_1$. Remove that cycle from the edge sequence you're accumulating and keep going along the walk, appending the edges to the sequence until you hit a vertex again that already occurs in the sequence. Again, the edges between those two occurrences form a cycle $C_2$, which is disjoint from $C_1$ simply because all the edges are distinct. If you keep going like this, adding $e_n$ closes a cycle $C_m$ comprising the entire remaining edge sequence, so removing it leaves all $n$ edges accounted for in the $m$ cycles.

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.