Return to Revisions

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question 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.