3
$\begingroup$

Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a_1, a_2, \dots, a_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of $a_1$ must equal the target vertex of $a_k$. My claim is that the multiset of arcs $W'=\{a_1, a_2, \dots, a_k\}$ can be partitioned into sets (not multisets) $W'_1, W'_2, \dots, W'_m$ such that the arcs in each $W'_i$ form a simple cycle.

There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.

I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You can state it and include the short proof. That's less trouble than finding some reference. If you want to try and find one, your claim is equivalent to the following: every graph in which all degrees are even has an edge-disjoint cycle cover. $\endgroup$
    – Yuval Filmus
    Feb 22, 2016 at 21:47
  • $\begingroup$ Isn't this just what you do for the decomposition of a Euler tour? $\endgroup$
    – G. Bach
    Feb 23, 2016 at 9:44

2 Answers 2

Reset to default
2
$\begingroup$

The problem stated in the question is also presented in the exercise of the book.

If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.

Improve this answer
$\endgroup$
0
$\begingroup$

Construct the graph $G = (V,E)$ such that $\forall \ v \in V, \ \exists \ a_i \in W$ such that $a_i$ is incident to $v$ and $E = W$ itself.

This graph $G$ will be connected. Now the multiset $W'$ is an Euler Tour in the graph hence the graph is Eulerian as well. Thus you can use the fact that if we have a cycle $C$ in an Eulerian graph, then the graph remains Eulerian even after removal of $C$.

Reference

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The OP already knows how to prove the claim. They're looking for a reference. $\endgroup$
    – Yuval Filmus
    Feb 23, 2016 at 7:09
  • $\begingroup$ @YuvalFilmus The link does kinda provide a reference, albeit not a very citable one $\endgroup$
    – David Richerby
    Feb 23, 2016 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.