Graph with the smallest diameter. Consider a graph with $N$ vertexes where each vertex has at most $k$ edges.
I assume that $k < N$. What is the graph which have above property and has the smallest diameter?
Also, could you suggest good books in graph theory. Thanks.

This question is quite difficult. The upper bound on the number of vertices given above by @Boris Novikov coincides with Moore's bound in the case of the Petersen graph. Moore's bound is not only achieved by the Petersen graph, but also by the Hoffman-Singleton graph, and in general, by the so-called Moore graphs. Unfortunately, there are very few Moore graphs. In most other cases, i.e. when Moore's bound cannot be reached, the optimal graph is not known. For more details see "Moore Graphs and Beyond: A survey of the Degree/Diameter Problem", by Mirka Miller and Josef Siran (Elec. J. Combinatorics, Dynamic Survey 14). 
