Consider the sparse \(G(n,p)\) model in which \(p = \frac{c}{n-1}\) for some constant \(c\).

Part A

Fix two nodes \(i\) and \(j\). Give a formula for the expected number of paths of length \(2\) between \(i\) and \(j\).

Part B

Markov’s inequality says that, if \(X\) is a nonnegative random variable and \(a > 0\), then

\[ \begin{aligned} \mathbb{P}(X \geq a) \leq \frac{\mathbb{E}[X]}{a}. \end{aligned} \]

Use Markov’s inequality to give an upper bound on the probability that there exists a path (just one!) of length \(2\) between two fixed nodes \(i\) and \(j\) in the sparse \(G(n,p)\) model. What happens to your bound as \(n\) grows large?