On deciding if a graph can be made given it's $m$ regular and having $n$ vertices Is there any theory which can tell us whether a graph can be made given that it is $m$-regular and has $n$ vertices
I tried making a 6-regular graph with 8 vertices by connecting to chords on the right, and it happens that 1 vertex remains.

 A: For this question, I'll assume that "graph" means "simple graph".

As pointed out in the comments, for an $m$-regular graph to have $n$ vertices, an obvious necessary condition is $m < n$. 

Thus, assume $m < n$.

If $m,n$ are both odd, then no such graph exists since the sum of the degrees is $mn$ which is odd, but for any simple graph, the sum of the degrees is equal to twice the number of edges, which therefore must be even. 

If $m,n$ are not both odd, such a graph always exists. Here's one way to construct such a graph . . .

Place the $n$ vertices in the plane, equally spaced around a circle.

Case $(1)\,$: $m$ is even. Connect each vertex to the $m/2$ closest vertices on the left, and also to the $m/2$ closest vertices on the right.

Case $(2)\,$: $m$ is odd. Since $m,n$ are not both odd, $n$ is even. Connect each vertex to the $(m-1)/2$ closest vertices on the left, and also to the $(m-1)/2$ closest vertices on the right. Also connect each vertex to its diametrically opposite vertex. 

To clarify, no need to do both left and right connections -- the left connections are accomplished automatically by the right ones (and vice-versa). In my two-way description, I was just describing which vertices are connected to a given vertex. For an actual construction, there's no need to draw an edge that's already been drawn.
