# Turning a regular directed graph into a regular graph

Let $$G$$ be a $$k$$-regular directed graph, that is, a directed graph such that each vertex has $$k$$ edges going in and $$k$$ edges going out of it, and suppose further that $$G$$ has no loops. We can associate a non-directed graph $$G'$$ to it by ignoring the directions and eliminating double edges. Then $$G'$$ is a graph with degrees between $$k$$ (if all the in and out edges collapse to the same) and $$2k$$ (the other extreme case).

Question: Is there a way to add edges to $$G'$$ to make it $$k'$$-regular, for some $$k'(k)$$ independent of the number of vertices? Clearly $$k' \geq 2k$$, but even something larger would work.

• Can you clarify $k'$? What exactly do you mean "independent of the number of vertices"? – Joey Kilpatrick Nov 5 '18 at 23:18
• I mean a function that only depends on the degree of the regular graph but not on the number of vertices. Otherwise, if $n$ is the number of vertices, you can clearly always add vertices to make it $(n-1)$-regular, i.e., complete. I would like something that only depends on $k$, like $3k, 10k$, even something like $k!$ or $e^k$ if it works... – frafour Nov 6 '18 at 6:33