0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.