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

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.

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.