Bounding the expected distance from two arbitrary nodes in a $k$-regular graph Consider a connected $k$-regular graph with $N$ vertices, and let $v'$ be some arbitrary vertex in this graph. Suppose we pick a vertex $v_r$ uniformly at random from all $N$ nodes. Prove that the expected distance from $v'$ to $v_r$ is $\Omega(\log_kN)$.
I am quite confused because it seems that there are many distinct $k$-regular graphs on $N$ vertices. Now, since I am putting a lower bound on the expected distance, is this just a matter of finding the 'best' graph to minimize the expected value; i.e., some graph with the property that most or all of its vertices are 'close' to $v'$, in comparison with all $k$-regular graphs on $N$ vertices?
 A: Here's the solution that goes along with my hint. Let $G=(V,E)$ be a $k$-regular graph and let $v'\in V$. For any $m\in\mathbb{N}$, define the (closed) ball of radius $m$ centered at $v'$ by
$$
B_m(v'):=\{v\in V: d(v,v')\leq m\},
$$
where $d(v,v')$ is the distance between $v$ and $v'$ in $G$. So, $B_m(v')$ consists of the vertices of $G$ that are at most a distance of $m$ away from $v'$.
Since $G$ is $k$-regular, there are $k$ vertices that are a distance of $1$ from $v'$. Thus, $|B_1(v')|=k+1$ (since we also count $v'$, which is obviously distance $0$ from itself). Each vertex in $B_1(v')$ is adjacent to $k$ vertices, and thus we have the crude bound
$$
|B_2(v')|\leq k|B_1(v')|+|B_1(v')|=k(k+1)+(k+1)=(k+1)^2.
$$
A simple induction continuing in this manner shows that $|B_m(v')|\leq (k+1)^m$ for all $m\in\mathbb{N}$.
As a consequence, if $m=\log_{k+1}(\lfloor |V|/2 \rfloor)$, then 
$$
m=\frac{\log(\lfloor |V|/2 \rfloor)}{\log(k+1)}\cdot\frac{\log(k+1)}{\log{k}}\cdot \frac{\log{k}}{\log(k+1)}=\log_k(\lfloor |V|/2 \rfloor)\cdot\frac{\log{k}}{\log(k+1)}=\Omega(\log_k|V|),
$$
and $|B_m(v')|\leq \lfloor |V|/2 \rfloor\leq |V|/2$. So at most half of the vertices of $G$ are within a distance of $m$ from $v'$. This implies that at least half of the vertices in $G$ are distance $\Omega(\log_k|V|)$ from $v'$. Thus, the average distance of a vertex from $v'$ is at least $\frac{1}{|V|}\cdot \frac{|V|}{2}\cdot m=\frac{1}{2}\cdot m$, which is $\Omega(\log_k|V|)$.
