Randomly removing edges from a graph so that each vertex has N edges

Question

I am an engineer working on an algorithm that solves a system of equations, where each equation is associated with an edge on a graph. Currently I am running the algorithm on a graph which has an edge between every pair of vertices (a complete graph, I believe?), but I am hoping to study the error and convergence for cases when there are fewer edges. However, when any vertex has fewer than 4 edges, the system will not converge, so I want to avoid such cases.

Is there a method to remove edges from a complete graph, such that every vertex has N edges? If not, is there anything that gets close, giving each vertex, say, N +/-M edges?

Thanks for any guidance.

Answer 1

If the number of vertices $V$ is prime and $N$ is even, you can number the vertices from $0$ to $V-1$ and choose $\frac N2$ pairwise coprime numbers, no pair of which adds to $V$. Add and subtract each of your $\frac N2$ numbers from each vertex number $\bmod V$, keep the edges indicated, and you will have a graph that meets your requirement. All these graphs will have a similar structure of being $\frac N2$ cycles that are interlaced. That might or might not be a problem for you. If $V$ is not prime you can do the same if you can find $\frac N2$ numbers that are pairwise coprime and coprime to $V$ with no pair summing to $V$. As long as $N$ is not too large this should be possible.