1

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.

hannahh
  • 589

1 Answers1

3

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • I get it now, thanks! – hannahh Apr 02 '13 at 17:18
  • 1
    Related answer: How to prove $G$ is Eulerian – MJD May 06 '14 at 20:57
  • 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. – funda Jan 28 '18 at 15:48
  • @funda This question asks about graphs where every vertex has outdegree equal to its indegree. In such a graph, what you suggested is impossible. – MJD Jan 28 '18 at 17:16
  • 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$. – funda Jan 28 '18 at 17:24
  • I guess nowhere it says the cycles have to be simple, but then in your algorithm you should mention that you don't walk over already visited edges. – funda Jan 28 '18 at 17:32
  • I didn't say to take the first simple cycle. I said "walk until you come back to $v$". Your example doesn't do this. – MJD Jan 28 '18 at 18:22