# Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?

Ideally, such an algorithm would not be a brute force one. Is there a clever way to do this?

The complete bipartite graph $K_{k,k}$ has $2k$ vertices, each of which has degree $k$.

If $k$ is odd, take the complete graph on $k+1$ vertices. If $k$ is even, take the complete graph on $k+2$ vertices numbered $1,\ldots,k+2$, and disconnect the $k/2+1$ edges $(1,2),(3,4),\ldots,(k+1,k+2)$.

It is not hard to check that these graphs have the minimal number of vertices, and are moreover unique (up to isomorphism) for this property.