# Veblen's theorem for digraphs

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.
• Related answer: How to prove $G$ is Eulerian – MJD May 6 '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
• 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