Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$. I want to know what is the expected number of vertices a distance $k$ away (where distance means the shortest distance). I can only figure out that we expect there to be $(n-1)p$ vertices a distance 1 away since each of the possible $(n-1)$ edges outgoing from $u$ have probability $p$ of existing, but I am having trouble generalizing from this local property. Maybe someone can handle the task or perhaps point me in the right direction via a paper?
If it makes it easier, assume that $G$ is connected (as it almost surely is as $n\rightarrow \infty$, which is the case I am interested about). As a subproblem of almost equal importance, I would in particular like to know what is the expected longest shortest distance from vertex $u$ and how many vertices are away from vertex $u$ at that distance (subproblem with the maximum possible $k$).
Note: (1) The graph does not have a bound on the degree of the vertex (there could be as many as $n-1$ adjacent vertices to $u$).
Best Answer
Let $\lambda=np$. Then the average distance $k$ between two randomly picked vertices from the giant component is $$ k\sim \frac{\log n}{\log \lambda}, $$ given that the giant component exists ($\lambda>1$). A proof can be found in, e.g., Durrett's Random graph dynamics.
This result implies that the actual number for your first question is $$ \lambda^k. $$ However, this only works if $pn\to\lambda<\infty$ when $n\to\infty$. What about the case $p=const$? Here is an exercise: Show that the diameter of the E-R random graph in this case is 2 a.a.s.
For the diameter (the largest among the shortest paths) the question is more subtle. A nice review is given in Complex Graphs and Networks bu Lu and Chung, and the answer depends on the parameters.