# Prove that there exists a set $\{C_1,\ldots,C_m\}$ of cycles in $G$.

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!

-
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

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.