If we are given a random graph G, where edges are made with probability $ \frac{1}{2}$.
A) What's the probability that $2$ different vertices have a path of length 2 between them.
B) What is the expected value of the number of paths of length 2 in the graph.
For A, would it simply be $ (\frac{1}{2})^2$ ?
For B, I know that there are (n-2) ways to choose a third vertex and that the probability of all three being connected is $ \frac{1}{2}^2$ but I am stuck.
On
Let $G(n+2,p)$ be a random graph of $n+2$ vertices where each edge is generated with probability $p$.Let $P'$ be the probability that there is no path of length $2$ between two chosen vertices.
Let $x,y$ be the chosen vertices. For any of the $n$ remaining vertices, say $z$, the probability that there is no length 2 path $x<->z<->y$ would be $1-p^{2}$.
So, $P' = (1-p^{2})^{n}$
So, the probability that there is a path of length 2 between any two chosen vertices is $1-P'=1-(1-p^{2})^{n}$.
Choosing $p=\frac{1}{2}$ would give you the required answer above.
As for the expected number of paths of length 2, consider two vertices $v$ and $w$, we'll find the expected number of paths of length 2 between these two vertices. Let $z$ be some other vertex. The probability that $v <-> z <-> w$ is an actual path in the graph is $\frac{1}{4}$.
So, we consider all such $v <-> z <-> w$. How many are there?, the answer is quite simple, it is the number of choices of $z$, i.e $n$.
Finally, the number of ways we can select two vertices is $C(n+2;2)$ so the expected number is:
$E = C(n+2;2) \sum\limits_{i=1}^{n}1.\frac{1}{4}=C(n+2;2)\frac{n}{4}$
You need to count the possible two-edged paths between two particular vertices (ie: how many other vertices are there in the graph) and determine the probability that at least one among these paths is made.
You need to count the number of pairs, determine the expected count of length-2 paths between each pair, and then apply the linearity of expectation.