Generating Random Constrained Graph

I need to generate a randomized graph with a fixed number of vertices. I'm having some difficulty getting a solution every time. Any help would be appreciated.

Graph Rules

1) Each Vertex will have a random number of connections that is at most N-1 where N is the total number of vertices.

2) The Vertices cannot contain direct connections to themselves

3) The vertices cannot contain duplicate connections to other vertices.

4) If a vertex A is connected to Vertex B then Vertex B must connect to Vertex A.

I'm getting a correct solution about 70% of the time, but other times I get fairly far into the graph then no valid vertices are left. What constraints on the vertex connections do I need to guarantee a solution?

What I'm doing so far

1) Check that the total number of connections is even. If A points to B and B points to A then the total number of connections in the graph should be even or else there is no solution. If it is odd modify a vertex so the total number is even.

2) Fill in each vertex that is fully constrained. So a vertex that has N-1 connections must point to ALL other vertices. Fill in a connection from that vertex to all others and give all other vertices a connection to the fully constrained ones.

3) Process each vertex by how tightly it is constrained. So process all vertices with N-2 connections then, N-3 connection, then N-4, etc by generated random vertex indexes.

4) If The new random index is valid connect them then continue, if it is not valid rerandom the index until you get a valid value. (The graphs are only going to be 7-15 nodes or so maximum so this doesn't take extremely long).

Generally I get to the last 1 or 2 vertices but then have no valid values left with this method. Anyone have a better algorithm or an additional constraint on the number of connections values that would help me out?