Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to build a graph with number of vertexes N such that each vertex has degree at least k and the graph has the smallest diameter. I believe that this question should be well studied.

EDIT: yes complete graph is an answer, but not interesting. I am changing the question a little bit: each vertex has degree k.

share|cite|improve this question
This is almost a good question. The problem is that it appears you have put almost no effort into the question yourself. May I suggest including (a) necessary conditions on the existence of k-regular n-vertex graphs (b) resolving the 1-regular, 2-regular, (n-1)-regular and n-regular cases. Note, that PhD theses are written about the degree-diameter problem, and this is not far off -- it might be difficult to answer this question just for 3-regular (cubic) graphs. – Douglas S. Stones Oct 25 '12 at 21:13

The complete graph on $N$ vertices, $K_N$, will be hard to beat. If $k \gt N-1$ are you allowed multiple edges between a given pair of vertices? I hope so.

share|cite|improve this answer
well, k < N - 1 – ashim Oct 25 '12 at 19:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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