I hope you have nothing against ants: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=357291

Answer is $27$. Consider the following graph ($K_i$ represents a clique with $i$ vertices) \[K_3\ \ K_5 \ \ \underbrace{K_2 \ \ K_3 \ \ K_3}_{1}\ \ \underbrace{K_2 \ \ K_3 \ \ K_3}_{2}\ \ \underbrace{K_2 \ \ K_3 \ \ K_3}_{3}\ \ \dots \ \ \underbrace{K_2 \ \ K_3 \ \ K_3}_{8} \ \ K_5 \ \ K_3 \]and adjacent cliques are connected for lower bound. Let $A$ be any vertex and $T_i$ be the set of vertices where distance of the shortest path between $A$ and them are $i$. Note that $T_i$ and $T_{i+m}$ have no edge between them for $m\geq 2$. Let the last one be $T_m$. Since any vertex in $T_m$ is neighbour with a vertex in $T_m$ or $T_{m-1}$, we have $|T_{m-1}|+|T_m|-1\geq7$ or $|T_{m-1}|+|T_m|\geq 8$. Also $A'$s degree is at least $7$ hence $|T_1|\geq 7$. A vertex in $T_i$ can be neighbour with only a vertex in $T_{i-1},T_i,T_{i+1}$ thus, $|T_{i-1}|+|T_i|+|T_{i+1}|\geq 8$. Suppose that $m\geq 28$. \[1+\sum_{i=1}^{m}{|T_i|}=(1+|T_1|)+\sum_{i\equiv 0(mod \ 3)}^{24}{(|T_{i-1}|+|T_i|+|T_{i+1}|)}+\sum_{i=26}^{m-2}{(|T_i|)}+(|T_{m-1}|+|T_m|)\geq \sum_{i=26}^{m-2}{|T_i|}+80>80\]Which results in a contradiction as desired.$\blacksquare$