2 better, explicit construction

In that case, the answer is given by http://mathoverflow.net/questions/48702 You call the vertices of your graph red, and you want to have a collection of blue vertices, so that the degree of every red vertex $v_i$ equals $r-d_i,$ where $d_i$ is the degree of $v_i$ in your graph $G.$ The degrees of the blue vertices are unspecified. The Gale-Ryser theorem (mentioned in the question cited above) tells you that this can be done.

EDIT Here is a better way: join every vertex $v_i$ to $r - d_i$ new vertices. When we are done, we have added $K=r n - \sum_i d_i$ new vertices. All of the old vertices now have degree $r,$ so we leave them be. The new vertices all have degree $1.$ If there exists a graph on $K$ vertices of degree $r-1,$ draw the edges of that graph between the corresponding new vertices, and we are done. If there is not such a graph, that means that either $K$ has the wrong parity, or is too small, but this is easy to fix by adding a few newer vertices (it is clear that we will never need to add more than $2r$ extra vertices, the precise bound is an exercise to the reader).

1

In that case, the answer is given by http://mathoverflow.net/questions/48702 You call the vertices of your graph red, and you want to have a collection of blue vertices, so that the degree of every red vertex $v_i$ equals $r-d_i,$ where $d_i$ is the degree of $v_i$ in your graph $G.$ The degrees of the blue vertices are unspecified. The Gale-Ryser theorem (mentioned in the question cited above) tells you that this can be done.