Ideally, such an algorithm would not be a brute force one. Is there a clever way to do this?
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.