Show that Random Graphs Typically Have Diameter 2 (Probabilistic Method)

Question

Show that random graphs typically have diameter 2. That is, the probability that $G_p$, the graph with p vertices, has diameter 2 converges to 1 as $p \rightarrow \infty$.

Hint: Find the probability that two given vertices have minimal distance > 2 in $G_p$; find the average number of such pairs in $G_p$; make a conclusion.

I could solve this problem if I knew the probability that 2 vertices have distance > 2 in $G_p$, but I don't see how to compute this. Could someone provide me with a nudge in the right direction to finding this probability, so that I can complete the proof?

Answer 1

"Distance between $w$ and $v$ is $>2$" can be rewritten as "$v$ and $w$ are not neighbors, and they also share no neighbors." Can you further write this event in terms of edges and compute the probability?

$$P(\text{$v$ and $w$ not neighbors}) \cdot [1 - P(\text{$u$ is a neighbor of both $v$ and $w$})]^{p-2} = (1/2) \cdot (3/4)^{p-2}$$

Then,

$$E[\text{number of pairs with distance $> 2$}] = \frac{p(p-1)}{2} P(\text{$w$ and $v$ have distance $>2$}) = \frac{p(p-1)}{2}\frac{1}{2} (\frac{3}{4})^{p-2}$$