Generating a random cubic graph with uniform probability (or less)

Question

While this may look like homework, I assure you it's not. It stems from some homework assignment I did, though.

Let's call an undirected graph without self-edges "cubic" if every vertex has degree exactly three. Given a positive integer N I'd like to generate a random cubic graph on N vertices. I'd like for it to have uniform probability, that is, if there are M cubic graphs on N vertices the probability of generating each one is 1/M. A weaker condition that is still fine is that every cubic graph has non-zero probability.

I feel there's a quick and smart way to do this, but so far I've been unsuccessful.

I am a bad coder, please bear with this awful code:

PRE: edges = (3*nodes)/2, nodes is even, the constants are selected in such a way that the hash works (BIG_PRIME is bigger than edges, SMALL_PRIME is bigger than nodes, LOAD_FACTOR is small).

void random_cubic_graph() {

int i, j, k, count;
int *degree;
char guard;

count = 0;
degree = (int*) calloc(nodes, sizeof(int));

while (count < edges) {

    /* Try a new edge at random */

    guard = 0;
    i = rand() % nodes;
    j = rand() % nodes;

    /* Checks if it is a self-edge */

    if (i == j)
        guard = 1;

    /* Checks that the degrees are 3 or less */

    if (degree[i] > 2 || degree[j] > 2) 
        guard = 1;

    /* Checks that the edge was not already selected with an hash */

    k = 0;
    while(A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
        if (A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == j)
            if ((A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - j) / SMALL_PRIME == i)
                guard = 1;
        k++;
    }

    if (guard == 0)
        A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(i,j);

    k = 0;
    while(A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
        if (A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == i)
            if ((A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - i) / SMALL_PRIME == j)
                guard = 1;
        k++;
    }

    if (guard == 0) 
        A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(j,i);

    /* If all checks were passed, increment the count, print the edge, increment the degrees. */

    if (guard == 0) {
        count++;
        printf("%d\t%d\n", i, j);
        degree[i]++;
        degree[j]++;
    }

}

The problem is that its final edge that has to be selected might be a self-edge. That happens when N - 1 vertices have already degree 3, only 1 has degree 1. Thus the algorithm might not terminate. Moreover, I'm not entirely convinced that the probability is uniform.

There's probably much to improve in my code, but can you suggest a better algorithm to implement?