Graph decomposition into paths Let $G$ be a $(2k+1)$-regular graph on $n$ vertices. A theorem by Lovasz implies that $G$ decomposes into $\frac{1}{2}n$ disjoint paths. 
Since the number of edges is $\frac{1}{2}n(2k +1)$, is it possible to require that each path in the decomposition be of size $(2k +1)$.
I found an argument for the case when the graph $G$ has a perfect matching and its girth $\geq 2k +1$. Is there any literature on this.
 A: The question is "no" in general, as Gjergji pointed out.  The question of when the answer is "yes" is difficult and only partial results are known. It is conjectured that having a 1-factor is sufficient. A recent paper that discusses the issue is this paper of Odile Favaron, François Genest and Mekkia Kouider. Here is the abstract:
Kotzig asked in 1979 what are necessary and sufficient conditions
for a $d$-regular simple graph to admit a decomposition into paths
of length $d$ for odd $d\gt 3$. For cubic graphs, the existence of a 1-factor is
both necessary and sufficient. Even more, each 1-factor is extendable to a
decomposition of the graph into paths of length 3 where the middle edges
of the paths coincide with the 1-factor. We conjecture that existence of a
1-factor is indeed a sufficient condition for Kotzig’s problem. For general
odd regular graphs, most 1-factors appear to be extendable and we show
that for the family of simple 5-regular graphs with no cycles of length
4, all 1-factors are extendable. However, for $d\gt 3$ we found infinite families of $d$-regular simple graphs with non-extendable 1-factors. Few authors
have studied the decompositions of general regular graphs. We present
examples and open problems; in particular, we conjecture that in planar
5-regular graphs all 1-factors are extendable.
Finally, I should mention that I'm not a specialist in this area so my assertion that the problem is still unsolved is not gospel.
A: The answer in general is no. Already in the case $k=1$, a cubic graph is the disjoint union of paths of length $3$ if and only if it has a perfect matching. Proof: If the graph has a decomposition into paths of length $3$, take the middle edges. This will give you a perfect matching. For the other direction, suppose you have a perfect matching $M$. The complement of $M$ is a union of cycles which we can orient arbitrarily. Now to each edge in $M$ assign an outgoing and an incoming edge.
Determining which graphs admit decompositions into paths of length $k$ seems to be hard in general. In addition to the conjectures mentioned in Brendan Mckay's answer let me mention another closely related conjecture. Let's call a $k$-PPDC (perfect path double cover) a decomposition of the edges of our graphs taken with multiplicity 2, into paths of length $k$ so that each vertex appears exactly twice as an endpoint of such a path. It is conjectured that every k-regular graph admits a k-PPDC (see "Perfect path double covers of graphs" by J.A. Bondy where this conjecture is proved for k-regular graphs of girth greater than k). Notice that for $(2k+1)$-regular graphs, a  path decomposition as in your problem implies a $(2k+1)$-PPDC. I don't even know the answer to this weaker conjecture for $k\geq 2$: If a $(2k+1)$-regular graph has a perfect matching, does it have a $(2k+1)$-PPDC?
