# Constructing a graph of min-degree k with the smallest diameter possible

I need to build a graph with $N$ vertices such that each vertex has degree at least $k$ and the graph has the smallest diameter. What algorithm can I use?

-

## migrated from cstheory.stackexchange.comNov 15 '12 at 0:07

This question came from our site for theoretical computer scientists and researchers in related fields.

If $N > k$ then the complete graph $K_N$ is regular with degree $N-1 \geq k$, and has the smallest possible diameter $1$. If $N \leq k$ then there the degrees are bounded by $N-1 < k$, and so no such graph exists.