Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be decomposed into k directed 2-factors? And if it is true where can I find a proof for it?
1 Answer
$\begingroup$
$\endgroup$
It is true. In order to find a 2-factor in a regular directed graph, you need to associate an outneighbour to any vertex, in such a way that two vertices select different outneighbours.
Use Hall's theorem to obtain that. Hall's theorem always works on regular bipartite graph.