Erdős–Rényi $G(n,p)$ model, probability of given geodesic distance The $G(n,p)$ model describes a graph of $n$ nodes, where each pair of nodes are connected by an edge with an independent probability $p$. 
Would like to confirm my solution to a couple of question:


*

*If $p=\frac{1}{2}$, then show that as $n \rightarrow \infty$, the probability that nodes u and v, chosen uniformly at random, are at geodesic distance 2 tends to $\frac{1}{2}$.

*If the mean degree $c>0$ is fixed so that $p(n)=\frac{c}{n-1}$, then show that for each $k \in \mathbb{N} $, that $Pr[d(u,v)=k] \rightarrow 0$ as $n \rightarrow \infty$. Where $d(u,v)$ denotes geodesic distance between $u,v$.


My attempt:
Given $u$ and $v$,
$Pr[d(u,v)=2] = Pr(\nexists \,a \,path\,of\,length\,1)\times Pr(\exists\,path\,of\,length\,2)$
$Pr(\nexists \,a \,path\,of\,length\,1) = \frac{1}{2}$
$Pr(\exists\,path\,of\,length\,2) = 1 - Pr(\nexists \,a \,path\,of\,length\,2)$
There are $n-2$ potential paths of length 2. Each doesn't exist with probability $1-(\frac{1}{2})^{2}=3/4$. So the probability that there are no paths of length 2 is $\frac{3}{4}^{n-2}$. So
$Pr(\exists\,path\,of\,length\,2) = 1-\frac{3}{4}^{n-2}$
And $Pr[d(u,v)=2] = \frac{1}{2}(1-\frac{3}{4}^{n-2}) \rightarrow 1/2 \, as \, n \rightarrow \infty$
Letting now $p=\frac{c}{n-1}$, the probability that $u,v$ have a path of length $k$ is 
$p^{k}(n-2)\cdots(n-k) = \frac{c^{k}}{(n-1)^{k}}(n-2)\cdots(n-k) \rightarrow \frac{c^{k}}{n-1} \rightarrow 0$ as $n \rightarrow \infty$ 
Given that probability a path of length $k$ exists between $u,v$ tends to 0, the probability that $u,v$ are of distance $k$ also tends to 0.
 A: Essentially correct, though there is a nitpick to be made. 
For part 2, the expression
$$p^k (n-2)(n-3) \dotsm (n-k)$$
does not represent the probability that there is a path from $u$ to $v$ of length $k$. Rather, it represents the expected number of such paths: there are $(n-2)(n-3)\dotsm (n-k)$ paths of length $k$ from $u$ to $v$ in the complete graph $K_n$, and each one is present in the graph $G(n,p)$ with probability $p^k$.
Now, the expected number of paths is always an upper bound on the probability that there's at least one path, by the simple inequality
$$
  \Pr[X\ge 1] = \sum_{i=1}^\infty \Pr[X=i] \le \sum_{i=1}^\infty i \cdot \Pr[X=i] = \mathbb E[X].
$$
So if you show that the expected number of paths goes to $0$ as $n \to \infty$, then the probability also approaches $0$ (by the squeeze theorem: the most useful theorem in the study of random graphs). So your approach is valid. But it's important to keep the distinction between probability and expectation straight in general.
