I want to generate a r-regular graph with n vertices. rn = 2m.
(1) take n vertices; randomly pick a vertex v of degree < r. (2) S = set of all vertices of degree < r, and not a neighbor of v. (3) create an edge between v and a random element of S. (4) repeat.
Is there a more parallel way to do this?
Suppose I wanted to randomly pick an element in [1...n]. I could do it sequentially like:
take 1 w/ prob 1/n else take 2 w/ prob 1/n-1 else take 3 w/ prob 1/n-2 ...
Or I could do it "one shot" by generating a random element between [1...n].
Similarly, I want to generate a r-regular graph "one shot" rather than an single edge at a time.
This is to build mental intuition of what it means to "uniformly pick a r-regular graph."