The diameter of a specific 3-regular graph On my HW assignment we were asked to prove the following claim:

Let $G=(V,E)$ be a $3$-regular graph, and $m$ a natural number so that
  $n=|V|\geq 3(2^m)-1$. Prove that the diameter of $G \geq m+1$.

Can anyone can help with the solution or even with a way of approaching this prove?
 A: Start from any vertex $v$.  Construct sets $D_1$, $D_2$, ... in which $D_{k}$ contains all the vertices in $G$ that are at distance $k$ from $v$.  If the diameter is at most $m$ then $D_{k}=\emptyset$ whenever $k\geq m+1$ because there are no vertices at distance $k$ (note that this would be true from any $v$).  Basically, all we need to do is show that $D_{m+1}$ is not the empty set.
Since $G$ is $3$-regular, you know that $D_1$ contains exactly 3 vertices.  With the benefit of hindsight we can say $|D_1|=3\cdot 2^{0}$.
Each vertex in $D_1$ has 2 neighbors which are not vertex $v$.  These neighbors are either other vertices in $D_1$, or vertices in $D_2$.  Thus, there are at most $2\cdot |D_1|=3\cdot 2^{1}$ vertices in $D_2$.  I.e. $|D_2|\leq 3\cdot 2^{1}$.
Similarly, each vertex in $D_2$ has 3 neighbors.  One of those neighbors must be in $D_1$.  At most 2 of those neighbors are in $D_{3}$.  Thus we have
that $|D_3|\leq 2|D_2|\leq 3\cdot 2^{2}$.
Inductively, each vertex in $D_{k}$ has at least one neighbor in $D_{k-1}$ and hence at most 2 neighbors in $D_{k+1}$.  Thus $|D_{k+1}|\leq 2|D_{k}|\leq 3\cdot 2^{k}$.
Now, what is the most vertices $G$ can have if $|D_{m+1}|=0$?
\begin{align*}
|G| &= 1 + |D_1|+|D_2| + ... + |D_{m}| \\
    &\leq 1 + 3 + 3\cdot 2^1 + ... + 3\cdot 2^{m-1} \\
    &=1 + 3\left(\sum_{k=0}^{m-1}2^{k}\right) \\
    &=1 + 3(2^{m}-1) \\
    &=3\cdot 2^{m} - 2.
\end{align*}
But, your graph has more vertices than that.  So $|D_{m+1}|>0$ and hence the diameter of the graph is at least $m+1$.
