What are the rules for the regularity of a graph? For example, a 3-regular (degree 3 from each vertex) graph works for 8 vertices as well as 4 vertices and for 6 vertices.
Is it that for an odd regularity graph, any even number of vertices will fit as long as the number of vertices is larger than the regularity? So in the example above the regularity of 3 will work with 4, 6, and 8 vertices. Odd regularity and even number of vertices works with it. Is this a pattern that goes to infinity?
On
For a graph $G=(V,E)$ with $|E|=m$ and $|V|=n$, the handshaking says $\sum_{v\in V}\deg(v)=2m$. So if $G$ is $k$-regular, we must have $kn=2m$. Hence $kn$ must be an even number. Of course we must also have $k\leq n-1$ if $G$ is to be simple.
So notice that if $k=3$, then $n$ must even.
The above only says that $nk$ being even is a necessary condition. But it is also sufficient. This can be shown by actually constructing $k$-regular graph on $n$ vertices when $nk$ is even and $k\leq n-1$. For a construction, see Gerry Myerson's answer here.
The reason why 3 regularity works for 4, 8, 12, 16, etc. is that $K_4$ is a complete graph on four vertices such that every vertex has degree three. So if your graph has all of its components as $K_4$'s, then you can easily see that you can have any number of $K_4$'s and your graph with be three-regular. In general, this is the same for any $n-$regular graph. Take $m$ $K_n$'s to be components for your graph. Then your graph with be $n-1$ regular and will consist of $m\cdot n$ many vertices. In this manner, an "even" $2k$-regular graph will imply that your graph is composed of some amount of $K_{2k+1}$'s, and an "odd" $2k-1$ regular graph will consist of a bunch of $K_{2k}$'s, etc.