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?
 A: Once you have an initial $k$-regular graph, you can generate many more by randomly applying the following simple switching operation:

provided it does not introduce a parallel edge or loop.
A: I just finished this question from Allen Downey's book Think Complexity, and thought I'll just share my algorithm (which is the same as Gerry's answer but just fleshed out) :
Preconditions: 0 < k and k < n
**If n is odd, k must be even
Number of Vertex (n) : Possible Number of degrees for each Vertex (k)
                  2  :  1
                  3  :  2
                  4  :  1,2,3
                  5  :  2,4
                  6  :  1,2,3,4,5
                  7  :  2,4,6
                  8  :  1,2,3,4,5,6,7
                  9  :  2,4,6,8
                 10  :  1,2,3,4,5,6,7,8,9

Examples:
if n is 7:
    if k is 2:
        make_edge_for_each_vertice_x_steps_away(1)
    if k is 4:
        make_edge_for_each_vertice_x_steps_away(1)
        make_edge_for_each_vertice_x_steps_away(3)
    if k is 6:
        make_edge_for_each_vertice_x_steps_away(1)
        make_edge_for_each_vertice_x_steps_away(3)
        make_edge_for_each_vertice_x_steps_away(5)

if n is 8:
    if k is 1:
        make_edge_for_each_vertice_x_steps_away(4)
    if k is 2:
        make_edge_for_each_vertice_x_steps_away(1)
    if k is 3:
        make_edge_for_each_vertice_x_steps_away(4)
        make_edge_for_each_vertice_x_steps_away(3)
    if k is 4:
        make_edge_for_each_vertice_x_steps_away(1)
        make_edge_for_each_vertice_x_steps_away(2)
    if k is 5:
        make_edge_for_each_vertice_x_steps_away(4)
        make_edge_for_each_vertice_x_steps_away(3)
        make_edge_for_each_vertice_x_steps_away(2)
    if k is 6:
        make_edge_for_each_vertice_x_steps_away(1)
        make_edge_for_each_vertice_x_steps_away(2)
        make_edge_for_each_vertice_x_steps_away(3)
    if k is 7:
        make_edge_for_each_vertice_x_steps_away(4)
        make_edge_for_each_vertice_x_steps_away(3)
        make_edge_for_each_vertice_x_steps_away(2)
        make_edge_for_each_vertice_x_steps_away(1)

make_edge_for_each_vertice_x_steps_away(x):
    for each vertice, adds an edge to a neighbor x steps away. 
    if x == 1, edges will be created between v1 and v2, v2 and v3,..., vn to v1

There is a pattern where 
-If n is odd, we add edges between vertices x positions away, where x is all odd numbers between 1 to k.
-If n is even, and k is even, we add edges between vertices x positions away, where x is a range of numbers starting from 1 to n/2, and the range of these numbers is limited by the number of even numbers from 1 to k, including k
-If n is even, and k is odd, we add edges between vertices x positions away,
where x is a range of numbers starting from n/2 to 1, and the range of these numbers is limited by the number of odd numbers from 1 to k, including k
Algorithm:
Layout_all_vertices_in_a_circle()
if n is even:
    if k is even:
        countEvenNumbers = n/2
        #add an edge for each even number between 1 to k, including k
        for i in range(countEvenNumbers):
            make_edge_for_each_vertice_x_steps_away(i+1)
    else if k is odd:
        countOddNumbers = ((n-1)/2) + 1
        #add an edge for each odd number between 1 to k, including 1 and k
        for i in range(countOddNumbers):
            make_edge_for_each_vertice_x_steps_away((n/2)-i)

if n is odd:
    for i in range(1, k):
        if i is odd:
            make_edge_for_each_vertice_x_steps_away(i)

Hope this helps!
A: 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. 
