# 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
This question was part of a class assignment due about 15 hours after it was originally asked. Learning is important, but cheating on your assignments doesn't help you learn, and can get you expelled. – user47877 Nov 2 '12 at 2:00
I agree completely. That's why I put the homework tag and asked for help. – Help Nov 2 '12 at 2:38

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.