Here is another problem from Bondy/Murty: Prove that

A directed graph admits a decomposition into directed cycles if and only if it is even.

Here a directed graph is even if all its vertices have the same in- and out-degree. This is the digraph-version of Veblen's theorem which is proved by induction in the book. I don't see how I can "convert" that proof into a proof for digraphs, and I can't come up with anything else.


Can you do it by induction? Say the graph has an edge. Then at least one vertex $v$ has outdegree ≥ 1. (Why?) So start at $v$ and walk until you come back to $v$. (Prove this must happen.) At this point you have found a cycle. Remove this cycle. If the graph has no more edges, you are done; otherwise, repeat.

  • $\begingroup$ I get it now, thanks! $\endgroup$ – hannahh Apr 2 '13 at 17:18
  • 1
    $\begingroup$ Related answer: How to prove $G$ is Eulerian $\endgroup$ – MJD May 6 '14 at 20:57
  • $\begingroup$ Note that when finding a cycle like this you don't necessarily come back to $v$ itself, but you return to some vertex you have already visited. $\endgroup$ – funda Jan 28 '18 at 15:48
  • $\begingroup$ @funda This question asks about graphs where every vertex has outdegree equal to its indegree. In such a graph, what you suggested is impossible. $\endgroup$ – MJD Jan 28 '18 at 17:16
  • $\begingroup$ If we take the graph on vertices $1,2$ and $3$ with edges $(1,2), (2,3), (2,1),(3,2)$, your walk might do: $1,2,3,2$, and so the first simple cycle you find is $2,3,2$. $\endgroup$ – funda Jan 28 '18 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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