How to construct a k-regular graph?

I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical material on regular graphs on the internet but I can't seem to extract construction rules for regular graphs.

My preconditions are

k<n and (n%2 == 0 or k%2 == 0)


Is an adjacency matrix the way to go here? If so, how would I use it?

Is this even a mathematical problem?

-

If $k=2m$ is even, put all the vertices around a circle, and join each to its $m$ nearest neighbors on either side.
If $k=2m+1$ is odd, and $n$ is even, put the vertices on a circle, join each to its $m$ nearest neighbors on each side, and also to the vertex directly opposite.
Note that for $k \gt 1$ the resulting $k$-regular graph is connected, because it contains the $n$-cycle solution given by $k=2$. – hardmath May 21 '12 at 3:29
Once you have an initial $k$-regular graph, you can generate many more by randomly applying the following simple switching operation: