0
$\begingroup$

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!

  • 0
    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=`.2012-11-01

1 Answers 1

1

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.