Take the 2-minute tour ×
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.

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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.