finding the probability of distance between 2 vertices in a random graph Let x and y be vertices in a random graph, find the probability that the distance between the two is 2.
If i am not mistaken, if the question was to find the probability that the distance between the two is 1, then it would be just 1/2 since the edge could be included in the graph or not, but now i, having a hard time to find the formula so that i would know what edges to to include/ not include in the event.
i was thinking maybe in the direction of exclusion inclusion to count all the possibilities that two edges are connecting the two through another vertice, but no luck.
thanks in adavance !
 A: We have a random graph $G(n,p)$ that has $n$ vertices and in which every possible edge occurs independently with probability $p$. We take two different vertices $x$ and $y$ from the graph and want to know the distance between them.
The probability of having distance 1 is $p$.
If the distance is not 1, then the distance is 2 if $x$ and $y$ are connected via a third vertex $z$. There are $n-2$ possible choices for a third vertex. For a certain choice of $z$, the probability that $x$ and $y$ are connected via $z$ is $p^2$. So, the probability that they aren't connected via that $z$ is $1-p^2$. So, the probability that $x$ and $y$ aren't connected via any of the possible vertices $z$ is $(1-p^2)^{n-2}$. So they are connected with probability $1-(1-p^2)^{n-2}$. We have to multiply this by $(1-p)$ to account for the probability of having distance 1. So the formula is:
$$P(\text{distance} = 2) = (1-p) \cdot (1 - (1-p^2)^{n-2})$$
Note that we can multiply all those probabilities because the events are independent, for example, the probability of $x$ and $y$ being connected via one vertex is independent from the probability of $x$ and $y$ being connected via an other vertex. Getting the probability of distance 3 is more complicated.
