Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary 
graph and apply the answer to question
http://mathoverflow.net/questions/64770/existence-of-a-nice-subset-of-edges-in-k-regular-simple-graphs.
It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.