# How can you construct 3-regular graphs with minimal diameter?

Given an even $N$, is it possible to procedurally construct a 3-regular graph $G$ with $N$ vertices such that the maximum distance between any pair of vertexes is the minimum possible for that $N$? I know that a cube, for example, is the solution for $N = 8$, but what about other N's?

• Having $\frac{3}{2}|V|$ edges is not equivalent to being 3-regular, are you focusing only on 3-regular graphs? Dec 31 '16 at 16:49
• Yes, I guess that is the name. Dec 31 '16 at 17:50

The interesting case is connected 3-regular graphs (otherwise the diameter is infinite). We can simply show that if $G$ is such a graph then $D(G)=\Omega\left(\log_2|V|\right)$, where $D(G)$ denotes the diameter of the graph $G$.
Suppose $D(G)=d$. Start at an arbitrary vertex $v\in V$ and begin counting the vertices of the graph by scanning $G$ using BFS originating at $v$. In the first step you encounter 3 vertices ($v$'s neighbors). If at the $i'th$ step you encountered $k$ new vertices, then at the $i+1$ step you will encounter at most $2k$ new vertices (you have three edges to choose from, but at least one will take you back to a vertex you have already met). After at most $d$ steps you will encounter all of $G$'s vertices. This yields the following inequality:
$|V|\le 1+\sum\limits_{i=1}^{d-1}3\cdot 2^{i-1}=1+3\cdot \left(2^{d-1}-1\right)$, hence $d=\Omega\left(\log_2|V|\right)$.
You can see from the above that if $G$ is a connected d-regular graph then $D(G)=\Omega\left(\log_{d-1}G\right)$.